題目資訊
源地址：尋找兩個正序陣列的中位數
給定兩個大小分別為 m 和 n 的正序（從小到大）陣列 nums1 和 nums2，請你找出并回傳這兩個正序陣列的中位數 ，
演算法的時間復雜度應該為 \(O(log (m+n))\)，
提示資訊
示例 1
輸入：nums1 = [1,3], nums2 = [2]
輸出：2.00000
解釋：合并陣列 = [1,2,3] ，中位數 2
示例 2
輸入：nums1 = [1,2], nums2 = [3,4]
輸出：2.50000
解釋：合并陣列 = [1,2,3,4] ，中位數 (2 + 3) / 2 = 2.5
提示
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
實作邏輯
歸并法
最先想到的解題方法就是，將兩個有序陣列合并成一個有序陣列，然后再對結果集計算中位數，這種方法算是一個比較直接的思路，
但是，合并兩個陣列是此方法最耗時的操作，并且達到 \(O(m+n)\) 的時間復雜度，因此，并不符合題目中演算法時間復雜度達到 \(O(log (m+n))\) 的要求，
而且，采用此方法的空間復雜度，也達到了 \(O(m+n)?\) 的程度，其空間占用也不算優，
package cn.fatedeity.algorithm.leetcode;
public class MedianOfTwoSortedArrays {
public double answer(int[] nums1, int[] nums2) {
int i = 0, j = 0;
int[] numbers = new int[nums1.length + nums2.length];
int index = 0;
while (i < nums1.length || j < nums2.length) {
if (i == nums1.length) {
for (int k = j; k < nums2.length; k++) {
numbers[index++] = nums2[k];
}
break;
} else if (j == nums2.length) {
for (int k = i; k < nums1.length; k++) {
numbers[index++] = nums1[k];
}
break;
}
if (nums1[i] < nums2[j]) {
numbers[index++] = nums1[i++];
} else if (nums2[j] < nums1[i]) {
numbers[index++] = nums2[j++];
} else {
numbers[index++] = nums1[i++];
numbers[index++] = nums2[j++];
}
}
if ((numbers.length & 1) == 0) {
// 陣列長度是偶數
int mid = numbers.length >> 1;
return (numbers[mid - 1] + numbers[mid]) / 2f;
} else {
return numbers[numbers.length >> 1];
}
}
}
雙指標
面對兩個陣列，也可以采用雙指標的方式，只要找到中位數的位置即可，由于兩個陣列的長度已知，因此中位數對應的兩個陣列的下標之和也是已知，
基本思路就是，通過雙指標將兩個陣列中較小的值一個一個地過濾掉，直到過濾到中位數的下標位置，即可得到兩個陣列的中位數，
整個方法相較歸并法更優，空間復雜度直接降到了 \(O(1)\) 的程度，在運行效率上，其只回圈了 \(\frac{m+n}2\) 次，但時間復雜度仍然是 \(O(m+n)\)，未達到題目中 \(O(log (m+n))\) 的要求，
package cn.fatedeity.algorithm.leetcode;
public class MedianOfTwoSortedArrays {
public double answer(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int len = m + n;
int mStart = 0, nStart = 0;
int left = 0, right = 0;
for (int i = 0; i <= len >> 1; i++) {
left = right;
if (mStart < m && (nStart >= n || nums1[mStart] < nums2[nStart])) {
right = nums1[mStart++];
} else {
right = nums2[nStart++];
}
}
if ((len & 1) == 0) {
return (left + right) / 2f;
} else {
return right;
}
}
}
二分查找
一般要求時間復雜度達到 \(O(log (n))\) 的題目，大部分都是可以使用二分的思想來求解，
這道題目也可以采用二分法來使時間復雜度達到 \(O(log (m+n))\) 的要求，但確實一個有點反思維邏輯的二分查找，
主要解題思路是，通過合并后的長度來確定 \(\frac{1}{2}\) 的選值，比較兩個陣列中的第 \(\frac{1}{2}\) 個值，較小的部分直接過濾掉，直到過濾掉 \(\frac{m+n}{2}\) 個數值，則兩個陣列剩下的第一索引則用來計算中位數，
package cn.fatedeity.algorithm.leetcode;
public class MedianOfTwoSortedArrays {
public double answer(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int total = len1 + len2;
int left = (total + 1) >> 1;
int right = (total + 2) >> 1;
if (left == right) {
return this.findK(nums1, 0, nums2, 0, left);
} else {
return (this.findK(nums1, 0, nums2, 0, left) + this.findK(nums1, 0, nums2, 0, right)) / 2.0;
}
}
private int findK(int[] nums1, int i, int[] nums2, int j, int k) {
if (i >= nums1.length) {
// num1 已經被過濾完
return nums2[j + k - 1];
} else if (j >= nums2.length) {
// num2 已經被過濾完
return nums1[i + k - 1];
}
if (k == 1) {
// 陣列中第一個數值比較
return Math.min(nums1[i], nums2[j]);
}
// 確定每次要比較的兩個值
int mid1 = (i + (k >> 1) - 1) < nums1.length ? nums1[i + (k >> 1) - 1] : Integer.MAX_VALUE;
int mid2 = (j + (k >> 1) - 1) < nums2.length ? nums2[j + (k >> 1) - 1] : Integer.MAX_VALUE;
if (mid1 < mid2) {
return findK(nums1, i + (k >> 1), nums2, j, k - (k >> 1));
} else {
return findK(nums1, i, nums2, j + (k >> 1), k - (k >> 1));
}
}
}
首發于翔仔的個人博客，點擊查看更多，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500434.html
標籤：其他
上一篇：leetcode 452. Minimum Number of Arrows to Burst Balloons 用最少數量的箭引爆氣球(中等)