力扣4题：寻找两个正序数组的中位数

2024-02-25 10:04
文章标签 数组 力扣 两个 寻找 正序 中位数

本文主要是介绍力扣4题：寻找两个正序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目描述】

（困难）给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

【解题代码】

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;// 采用归并比较算法，因为只需要取中位数，所以新建数组大小nums只需要nums1和nums2一半即可int len3 = (len1 + len2) / 2 + 1;int[] nums = new int[len3];int i1 = 0, i2 = 0, j = 0;// 采用归并比较算法，向数组nums按大小依次从nums1和nums2拷贝数据// 一直到nums1和nums2其中之一遍历完毕，或者新建数组已经塞满while (true) {if (i1 >= len1 || i2 >= len2 || j >= len3) break;if (nums1[i1] < nums2[i2]) {nums[j++] = nums1[i1++];} else {nums[j++] = nums2[i2++];}}// 如果新建数组还未塞满，则从未遍历完的数组中直接拷贝数据把新建数组塞满     if (j < len3) {if (i1 < len1) System.arraycopy(nums1, i1, nums, j, len3 - j);if (i2 < len2) System.arraycopy(nums2, i2, nums, j, len3 - j);}// nums1和nums2之和为偶数，则返回中间两数之和的平均数    if (((len1 + len2)) % 2 == 0) return (nums[len3 - 2] + nums[len3 - 1]) / 2.0;// nums1和nums2之和为奇数，则直接返回中间数    elsereturn nums[len3 - 1];
}

【解题步骤】

  1. 拿到题目可知，此算法可以用归并算法进行处理，因为只需要取中位数，所以新建数组大小nums只需要nums1和nums2一半即可 nums2[i2++]; 
     int len1 = nums1.length;int len2 = nums2.length;// 采用归并比较算法，因为只需要取中位数，所以新建数组大小nums只需要nums1和nums2一半即可int len3 = (len1 + len2) / 2 + 1;int[] nums = new int[len3];
  2. 采用归并比较算法，向数组nums按大小依次从nums1和nums2拷贝数据，一直到nums1和nums2其中之一遍历完毕，或者新建数组已经塞满 
    while (true) {if (i1 >= len1 || i2 >= len2 || j >= len3) break;if (nums1[i1] < nums2[i2]) {nums[j++] = nums1[i1++];} else {nums[j++] = nums2[i2++];}
}
  3. 如果新建数组还未塞满，则从未遍历完的数组中直接拷贝数据把新建数组塞满 
    if (j < len3) {if (i1 < len1) System.arraycopy(nums1, i1, nums, j, len3 - j);if (i2 < len2) System.arraycopy(nums2, i2, nums, j, len3 - j);
}
  4. 根据nums1和nums2之和为奇数还是偶数，返回相应的结果 
     // nums1和nums2之和为偶数，则返回中间两数之和的平均数if (((len1 + len2)) % 2 == 0)return (nums[len3 - 2] + nums[len3 - 1]) / 2.0;
// nums1和nums2之和为奇数，则直接返回中间数
elsereturn nums[len3 - 1];

【思路总结】

  1. 归并算法是数据结构排序算法中一个很重要的算法， 归并排序非常稳定，时间复杂度始终都是 N*logN，另外除了常规的数组排序之外，很多场景都可以应用到，比如笔者以前做过的远程和本地文件夹同步算法，就是两边文件名称数组，进行归并比较处理，大家要掌握这个算法思路以及应用技巧；
  2. 算法应用中，要根据实际情况进行改良，比如在这里因为是取中位数，因此不需要向普通的场景申请两个数组之和的空间，而只需要取一半即可

这篇关于力扣4题：寻找两个正序数组的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/745149。

相关文章

hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
寻找身高相近的小朋友

寻找身高相近的小朋友

题目描述: 小明今年升学到小学一年级，来到新班级后发现其他小朋友们身高参差不齐，然后就想基于各小朋友和自己的身高差对他们进行排序，请帮他实现排序。 输入描述: 第一行为正整数H和N，0<H<200，为小明的身高，0<N<50，为新班级其他小朋友个数。第二行为N个正整数H1-HN，分别是其他小朋友的身高，取值范围0<Hi<200(1<=i<=N)，且N个正整数各不相同。 输出描述: 输出
阅读更多...
两个月冲刺软考——访问位与修改位的题型(淘汰哪一页)；内聚的类型；关于码制的知识点；地址映射的相关内容

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页)；内聚的类型；关于码制的知识点；地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位：为1时表示在内存期间被访问过，为0时表示未被访问；修改位：为1时表示该页面自从被装入内存后被修改过，为0时表示未修改过。 置换页面时，最先置换访问位和修改位为00的，其次是01(没被访问但被修改过)的，之后是10(被访问了但没被修改过)，最后是11。 2.内聚的类型 功能内聚：完成一个单一功能，各个部分协同工作，缺一不可。 顺序内聚：
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...
两数之和--力扣1

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求，元素不能重复且不需要排序，我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中，使用目标值减去当前循环的nums[i]，得到差值，如果我们在map中能够找到这个差值，就说明存在两个整数的和为目标值。 如果没有找到，就将当前循环的nums[i]以及下标i放入map中，以便后续查
阅读更多...
计算数组的斜率，偏移，R2

计算数组的斜率，偏移，R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou
阅读更多...
C# double[] 和Matlab数组MWArray[]转换

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };
阅读更多...
PHP7扩展开发之数组处理

PHP7扩展开发之数组处理

前言 这次，我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下： <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2