LeetCode刷題實戰(zhàn)4：兩個正序數(shù)組的中位數(shù)
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做尋找兩個正序數(shù)組的中位數(shù)，這道題很有意思，我們先來看題面：
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
https://leetcode-cn.com/problems/median-of-two-sorted-arrays
翻譯
給定兩個大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。
請你找出這兩個正序數(shù)組的中位數(shù)，并且要求算法的時間復(fù)雜度為 O(log(m + n))。
你可以假設(shè) nums1 和 nums2 不會同時為空。
示例 1:nums1 = [1, 3]nums2 = [2]則中位數(shù)是 2.0示例 2:nums1 = [1, 2]nums2 = [3, 4]則中位數(shù)是?(2?+?3)/2?=?2.5
方法一：二分查找
給定兩個有序數(shù)組，要求找到兩個有序數(shù)組的中位數(shù)，最直觀的思路有以下兩種：
使用歸并的方式，合并兩個有序數(shù)組，得到一個大的有序數(shù)組。大的有序數(shù)組的中間位置的元素，即為中位數(shù)。
不需要合并兩個有序數(shù)組，只要找到中位數(shù)的位置即可。由于兩個數(shù)組的長度已知，因此中位數(shù)對應(yīng)的兩個數(shù)組的下標之和也是已知的。維護兩個指針，初始時分別指向兩個數(shù)組的下標 00 的位置，每次將指向較小值的指針后移一位（如果一個指針已經(jīng)到達數(shù)組末尾，則只需要移動另一個數(shù)組的指針），直到到達中位數(shù)的位置。
class?Solution?{
????public?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;
????????????double?median = getKthElement(nums1, nums2, midIndex + 1);
????????????return?median;
????????} else?{
????????????int?midIndex1 = totalLength / 2?- 1, midIndex2 = totalLength / 2;
????????????double?median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
????????????return?median;
????????}
????}
????public?int?getKthElement(int[] nums1, int[] nums2, int?k)?{
????????/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較
?????????* 這里的 "/" 表示整除
?????????* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個
?????????* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個
?????????* 取 pivot = min(pivot1, pivot2)，兩個數(shù)組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個
?????????* 這樣 pivot 本身最大也只能是第 k-1 小的元素
?????????* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"，剩下的作為新的 nums1 數(shù)組
?????????* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"，剩下的作為新的 nums2 數(shù)組
?????????* 由于我們 "刪除" 了一些元素（這些元素都比第 k 小的元素要?。?，因此需要修改 k 的值，減去刪除的數(shù)的個數(shù)
?????????*/
????????int?length1 = nums1.length, length2 = nums2.length;
????????int?index1 = 0, index2 = 0;
????????int?kthElement = 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;
????????????}
????????}
????}
}
本題還有第2個方法：劃分數(shù)組?，大家有興趣的自己去leetcode學(xué)習(xí)一下，今天文章就不說了，這個比較有難度 。
如果喜歡本文，請順手點個贊或者轉(zhuǎn)發(fā)吧。
上期推文：
LeetCode刷題實戰(zhàn)1：在數(shù)組上遍歷出花樣
LeetCode刷題實戰(zhàn)3：最長不重復(fù)子串