【問題描述】[困難]

給定兩個(gè)大小為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請你找出這兩個(gè)正序數(shù)組的中位數(shù)，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))。你可以假設(shè) nums1 和 nums2 不會(huì)同時(shí)為空。示例 1:nums1 = [1, 3] nums2 = [2]則中位數(shù)是 2.0 示例 2:nums1 = [1, 2] nums2 = [3, 4]來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays 著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

【解答思路】

1. 數(shù)組合并

兩個(gè)數(shù)組合并，兩個(gè)有序數(shù)組的合并也是歸并排序中的一部分。然后根據(jù)奇數(shù)，還是偶數(shù)，返回中位數(shù)
時(shí)間復(fù)雜度：O(N+M) 空間復(fù)雜度：O(1)

public double findMedianSortedArrays(int[] nums1, int[] nums2) {int[] nums;int m = nums1.length;int n = nums2.length;nums = new int[m + n];if (m == 0) {if (n % 2 == 0) {return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;} else {return nums2[n / 2];}}if (n == 0) {if (m % 2 == 0) {return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;} else {return nums1[m / 2];}}int count = 0;int i = 0, j = 0;while (count != (m + n)) {if (i == m) {while (j != n) {nums[count++] = nums2[j++];}break;}if (j == n) {while (i != m) {nums[count++] = nums1[i++];}break;}if (nums1[i] < nums2[j]) {nums[count++] = nums1[i++];} else {nums[count++] = nums2[j++];}}if (count % 2 == 0) {return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;} else {return nums[count / 2];} }

2. 雙指針

時(shí)間復(fù)雜度：O(N+M) 空間復(fù)雜度：O(1)

public double findMedianSortedArrays(int[] A, int[] B) {int m = A.length;int n = B.length;int len = m + n;int left = -1, right = -1;int aStart = 0, bStart = 0;for (int i = 0; i <= len / 2; i++) {left = right;if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {right = A[aStart++];} else {right = B[bStart++];}}if ((len & 1) == 0)return (left + right) / 2.0;elsereturn right; }

3. 求第 k 小數(shù) k/2

時(shí)間復(fù)雜度：O(log(m+n) 空間復(fù)雜度：O(1)

public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n = nums1.length;int m = nums2.length;int left = (n + m + 1) / 2;int right = (n + m + 2) / 2;//將偶數(shù)和奇數(shù)的情況合并，如果是奇數(shù)，會(huì)求兩次同樣的 k 。return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5; }private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {int len1 = end1 - start1 + 1;int len2 = end2 - start2 + 1;//讓 len1 的長度小于 len2，這樣就能保證如果有數(shù)組空了，一定是 len1 if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);if (len1 == 0) return nums2[start2 + k - 1];if (k == 1) return Math.min(nums1[start1], nums2[start2]);int i = start1 + Math.min(len1, k / 2) - 1;int j = start2 + Math.min(len2, k / 2) - 1;if (nums1[i] > nums2[j]) {return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));}else {return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));}}

4. 中位數(shù)

用完

長度相等


時(shí)間復(fù)雜度：O(N) 空間復(fù)雜度：O(1)

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int leftLength = nums1.length;int rightLength = nums2.length;// 為了保證第一個(gè)數(shù)組比第二個(gè)數(shù)組小(或者相等)if (leftLength > rightLength) {return findMedianSortedArrays(nums2, nums1);}// 分割線左邊的所有元素需要滿足的個(gè)數(shù) m + (n - m + 1) / 2;// 兩個(gè)數(shù)組長度之和為偶數(shù)時(shí)，當(dāng)在長度之和上+1時(shí)，由于整除是向下取整，所以不會(huì)改變結(jié)果// 兩個(gè)數(shù)組長度之和為奇數(shù)時(shí)，按照分割線的左邊比右邊多一個(gè)元素的要求，此時(shí)在長度之和上+1，就會(huì)被2整除，會(huì)在原來的數(shù)//的基礎(chǔ)上+1，于是多出來的那個(gè)1就是左邊比右邊多出來的一個(gè)元素int totalLeft = (leftLength + rightLength + 1) / 2;// 在 nums1 的區(qū)間 [0, leftLength] 里查找恰當(dāng)?shù)姆指罹€，// 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]int left = 0;int right = leftLength;// nums1[i - 1] <= nums2[j]// 此處要求第一個(gè)數(shù)組中分割線的左邊的值 不大于(小于等于) 第二個(gè)數(shù)組中分割線的右邊的值// nums2[j - 1] <= nums1[i]// 此處要求第二個(gè)數(shù)組中分割線的左邊的值 不大于(小于等于) 第一個(gè)數(shù)組中分割線的右邊的值// 循環(huán)條件結(jié)束的條件為指針重合，即分割線已找到while (left < right) {// 二分查找，此處為取第一個(gè)數(shù)組中左右指針下標(biāo)的中位數(shù)，決定起始位置// 此處+1首先是為了不出現(xiàn)死循環(huán)，即left永遠(yuǎn)小于right的情況// left和right最小差距是1，此時(shí)下面的計(jì)算結(jié)果如果不加1會(huì)出現(xiàn)i一直=left的情況，而+1之后i才會(huì)=right// 于是在left=i的時(shí)候可以破壞循環(huán)條件，其次下標(biāo)+1還會(huì)保證下標(biāo)不會(huì)越界，因?yàn)?#43;1之后向上取整，保證了// i不會(huì)取到0值，即i-1不會(huì)小于0// 此時(shí)i也代表著在一個(gè)數(shù)組中左邊的元素的個(gè)數(shù)//+1 防止死循環(huán)int i = left + (right - left + 1) / 2;// 第一個(gè)數(shù)組中左邊的元素個(gè)數(shù)確定后，用左邊元素的總和-第一個(gè)數(shù)組中元素的總和=第二個(gè)元素中左邊的元素的總和// 此時(shí)j就是第二個(gè)元素中左邊的元素的個(gè)數(shù)int j = totalLeft - i;// 此處用了nums1[i - 1] <= nums2[j]的取反，當(dāng)?shù)谝粋€(gè)數(shù)組中分割線的左邊的值大于第二個(gè)數(shù)組中分割線的右邊的值// 說明又指針應(yīng)該左移，即-1if (nums1[i - 1] > nums2[j]) {// 下一輪搜索的區(qū)間 [left, i - 1]right = i - 1;// 此時(shí)說明條件滿足，應(yīng)當(dāng)將左指針右移到i的位置，至于為什么是右移，請看i的定義} else {// 下一輪搜索的區(qū)間 [i, right]left = i;}}// 退出循環(huán)時(shí)left一定等于right，所以此時(shí)等于left和right都可以// 為什么left一定不會(huì)大于right?因?yàn)閘eft=i。// 此時(shí)i代表分割線在第一個(gè)數(shù)組中所在的位置// nums1[i]為第一個(gè)數(shù)組中分割線右邊的第一個(gè)值// nums[i-1]即第一個(gè)數(shù)組中分割線左邊的第一個(gè)值int i = left;// 此時(shí)j代表分割線在第二個(gè)數(shù)組中的位置// nums2[j]為第一個(gè)數(shù)組中分割線右邊的第一個(gè)值// nums2[j-1]即第一個(gè)數(shù)組中分割線左邊的第一個(gè)值int j = totalLeft - i;// 當(dāng)i=0時(shí)，說明第一個(gè)數(shù)組分割線左邊沒有值，為了不影響// nums1[i - 1] <= nums2[j] 和 Math.max(nums1LeftMax, nums2LeftMax)// 的判斷，所以將它設(shè)置為int的最小值int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];// 等i=第一個(gè)數(shù)組的長度時(shí)，說明第一個(gè)數(shù)組分割線右邊沒有值，為了不影響// nums2[j - 1] <= nums1[i] 和 Math.min(nums1RightMin, nums2RightMin)// 的判斷，所以將它設(shè)置為int的最大值int nums1RightMin = i == leftLength ? Integer.MAX_VALUE : nums1[i];// 當(dāng)j=0時(shí)，說明第二個(gè)數(shù)組分割線左邊沒有值，為了不影響// nums2[j - 1] <= nums1[i] 和 Math.max(nums1LeftMax, nums2LeftMax)// 的判斷，所以將它設(shè)置為int的最小值int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];// 等j=第二個(gè)數(shù)組的長度時(shí)，說明第二個(gè)數(shù)組分割線右邊沒有值，為了不影響// nums1[i - 1] <= nums2[j] 和 Math.min(nums1RightMin, nums2RightMin)// 的判斷，所以將它設(shè)置為int的最大值int nums2RightMin = j == rightLength ? Integer.MAX_VALUE : nums2[j];// 如果兩個(gè)數(shù)組的長度之和為奇數(shù)，直接返回兩個(gè)數(shù)組在分割線左邊的最大值即可if (((leftLength + rightLength) % 2) == 1) {return Math.max(nums1LeftMax, nums2LeftMax);} else {// 如果兩個(gè)數(shù)組的長度之和為偶數(shù)，返回的是兩個(gè)數(shù)組在左邊的最大值和兩個(gè)數(shù)組在右邊的最小值的和的二分之一// 此處不能被向下取整，所以要強(qiáng)制轉(zhuǎn)換為double類型return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;}} }

【總結(jié)】

1. 二分查找法 log復(fù)雜度

2.邊界復(fù)雜 多種情況 腦袋清晰

3.時(shí)間算法復(fù)雜度可以讓簡單題變復(fù)雜題

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
參考視頻與評(píng)論：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第4题][寻找两个正序数组中的中位数][二分查找][双指针]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。