😀前言
在本文中，我们将深入研究一种复杂的算法问题：查找两个有序数组的中位数。这是一个经典的计算问题，通常出现在编程面试和算法挑战中。我们将首先探讨一种常见的暴力解决方法，然后逐步引入更高效的解决方案，最终理解并实现官方的二分法算法。通过本文，您将获得对这一重要算法问题的深刻理解。
🧑个人简介：大家好，我是尘觉，希望我的文章可以帮助到大家，您的满意是我的动力😉😉
寻找两个有序数组的中位数
自己思路
就是暴力破解或者是数组合并然后排序
看不得还是分析官方打败100%的吧
class Solution { public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int l=nums1.length+nums2.length; int[] c = new int[l]; for (int i = 0; i < nums1.length; i++) { c[i]=nums1[i]; } for (int i =0,j=nums1.length; i <nums2.length; i++,j++) { c[j]=nums2[i]; } Arrays.sort(c); if (l % 2 != 0) { return c[l / 2 ]; } else { return (double) (c[l / 2] + c[l / 2 - 1]) / 2.0; } } }
官方思路
int midIndex = totalLength / 2; 这个意思是当二个数组的和是奇数时取中间的数
注意为什么后面需要+1 如 1 2 3是合为3但是我们上面/2的结果在java里面是1又因为我们需要中为数 所以我们在调用下面的函数的时候需要+1
当偶数的时候同理
🥰重点分析getKthElement方法
index1和index2官方没有解释说 这里我来分析一下 这个可以指的是老地址 也就是初始地址
因为后面我们需要排除前面的元素怎么排除呢 我们可以通过在增加一个地址 即为新地址
newIndex1和newIndex2来表示新地址
half这个相当于比k还一半的数那来截取
举个例子就明白了
假设两个有序数组如下：
两个有序数组的长度分别是 4 和 9，长度之和是 13，中位数是两个有序数组中的第 7 个元素，因此需要找到第 k=7 个元素。
比较两个有序数组中下标为 k/2−1=2的数，即 A[2] 和 B[2]，如下面所示：
在代码中 newIndex1=2 newIndex2=2 index1=0 index2=0
由于 A[2]>B[2]，因此排除 B[0] 到 B[2]，即数组 B 的下标偏移（offset）变为 3，同时更新 k 的值：k=k−k/2=4。
在代码中就是 k - = (newIndex1 - index1 + 1) ==k=7-3=4 相当于 中位数减去新地址和老地址的个数 比如 0 1 2 算几个 就是 3-0+1=3个
然后老地址移位 就相当于 下标偏移（offset）变为 3 就是 index2 = newIndex2 + 1==index2=2+1=3 在数组2中的值为4 这个+1的意思是截取3为从第4位算
下一步寻找，比较两个有序数组中下标为 k/2−1=1 的数，即 A[1]和 B[4]，如下面所示，其中方括号部分表示已经被除的数。
在代码中我们就得 half = k / 2结果为2; 然后 int newIndex2 = Math.min(index2 + half, length2) - 1;这个相当于就是截取了不算中括号的数组2中值为4的就是1号相当于数组中0号 然后新地址 就是 老地址+之前的half-1 相当于不算 [1 2 3] + half=2的元素还多了一个 所以需要减1 才满足 k/2−1=1的元素即为 即 A[1]和 B[4]
由于 A[1]
在代码中就是 pivot1 <= pivot2 比较值 （对应A[1]
下一步寻找，比较两个有序数组中下标为 k/2−1=0 的数，即比较 A[2]和 B[3]，如下面所示，其中方括号部分表示已经被排除的数。
在代码中就是如下图 原因前面已经很清楚了
由于 A[2]=B[3]，根据之前的规则，排除 A 中的元素，因此排除 A[2]，即数组 A\text{A}A 的下标偏移变为 3，同时更新 k 的值： k=k−k/2=1
在代码中就是
由于 k 的值变成 1，因此比较两个有序数组中的未排除下标范围内的第一个数，其中较小的数即为第 k 个数，由于 A[3]>B[3]，因此第 k 个数是 B[3]=4
在代码中就是
有以下三种情况需要特殊处理：
- 如果 A[k/2−1]或者 B[k/2−1]越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 k 的值，而不能直接将 k 减去 k/2。
- 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。
- 如果 k=1，我们只要返回两个数组首元素的最小值即可。
对应代码
解释一下为什么减1是因为k是从1开始算的到数组要-1
到此终于结束了 整个流程分析
建议看玩我这个流程在看官方的详细的流程分析虽然抽象一点 但是理解我的了再看官方的也不是很难 如果想多学一种可以去看官方视频建议理解这个之后在去看视频 和挑战 划分数组解法
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
总结
这个还是很绕了 可以自己debug一个一个的看然后再加上我上面的思路结合自己的理解加上每个变量的作用理解就可以解决了
public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int length1 = nums1.length, length2 = nums2.length; int totalLength = length1 + length2; if (totalLength % 2 == 1) { int midIndex = totalLength / 2; return getKthElement(nums1, nums2, midIndex + 1); } else { int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2; return (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0; } } public static int getKthElement(int[] nums1, int[] nums2, int k) { int length1 = nums1.length, length2 = nums2.length; int index1 = 0, index2 = 0; while (true) { // 边界情况 if (index1 == length1) { return nums2[index2 + k - 1]; } if (index2 == length2) { return nums1[index1 + k - 1]; } if (k == 1) { return Math.min(nums1[index1], nums2[index2]); } // 正常情况 int half = k / 2; int newIndex1 = Math.min(index1 + half, length1) - 1; int newIndex2 = Math.min(index2 + half, length2) - 1; int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; if (pivot1 <= pivot2) { k -= (newIndex1 - index1 + 1); index1 = newIndex1 + 1; } else { k -= (newIndex2 - index2 + 1); index2 = newIndex2 + 1; } } }
😄总结
在本文中，我们详细分析了查找两个有序数组的中位数问题。我们首先介绍了一种暴力破解的方法，然后深入研究了官方的二分法解决方案。我们解释了每个步骤的原理，并提供了清晰的代码示例。最后，我们强调了该算法的关键思想和特殊情况的处理方法。通过本文，您现在应该能够更自信地处理这个算法问题，并在面试或编程挑战中取得更好的表现。希望这篇文章对您有所帮助，谢谢您的阅读！
文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞
