- 尋找兩個正序陣列的中位數
給定兩個大小分別為 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 == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6<= nums1[i], nums2[i] <= 10^6
解題思路：
- 添加添加一個陣列nums
- 將nums1和nums2從左到右遍歷賦值給nums
- 考慮越界分別單獨列出m=nums1.length和n=nums2.length的情況
- 考慮是否為偶數輸出中位數
class Solution {
private static double findMedianSortedArray(int[] nums1, int[] nums2) {
int i = 0, m = 0, n = 0, l = nums1.length + nums2.length;
int[] nums = new int[l];
while (i < l) {
if (m == nums1.length) {
nums[i++] = nums2[n++];
if (n == nums2.length) break;
}
if (n == nums2.length) {
nums[i++] = nums1[m++];
if (m == nums1.length) break;
}
if (m < nums1.length && n < nums2.length)
nums[i++] = (nums1[m] < nums2[n]) ? nums1[m++] : nums2[n++];
}
for (int j = 0; j < l; j++) {
System.out.println(nums[j]);
}
//陣列時是否為偶數
if (l % 2 == 0)
return (double)(nums[l / 2-1] + nums[l / 2 ]) / 2.0;
return nums[(l + 1) / 2-1];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/413422.html
標籤：其他
上一篇：Linux學習筆記（8)
下一篇：＜2＞ 瀏覽檔案系統