ps:題目來自力扣

尋找兩個正序數組的中位數

給定兩個大小分別為?m?和?n?的正序（從小到大）數組?nums1?和?nums2。請你找出并返回這兩個正序數組的?中位數?。

算法的時間復雜度應該為?O(log (m+n))?。

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 為了讓二分查找的范圍更小，保證 nums1 是較短的數組if (nums1.length > nums2.length) {int[] temp = nums1;nums1 = nums2;nums2 = temp;}int m = nums1.length;int n = nums2.length;// 左半部分的元素數量，無論兩數組總長度奇偶，左半部分元素數量為 (m + n + 1) / 2int totalLeft = (m + n + 1) / 2;// 二分查找的左右邊界，在 nums1 的索引 0 到 m 之間查找分割線int left = 0;int right = m;while (left < right) {// nums1 的分割線位置int i = left + (right - left + 1) / 2;// nums2 的分割線位置，根據 left 部分元素總數確定int j = totalLeft - i;// 如果 nums1 分割線左邊的元素大于 nums2 分割線右邊的元素if (nums1[i - 1] > nums2[j]) {// 說明分割線 i 太靠右了，需要向左移動right = i - 1;} else {// 分割線 i 合適或者還可以往右移動left = i;}}// 最終確定的 nums1 分割線位置int i = left;// 最終確定的 nums2 分割線位置int j = totalLeft - i;// 計算分割線左右的四個關鍵元素int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];// 根據兩數組總長度的奇偶性計算中位數if ((m + n) % 2 == 1) {// 總長度為奇數，中位數是左半部分的最大值return Math.max(nums1LeftMax, nums2LeftMax);} else {// 總長度為偶數，中位數是左半部分最大值和右半部分最小值的平均值return (double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;}}
}