---

題目

• 原題連接：4. 尋找兩個正序數組的中位數

---

1- 思路

思路

• 將尋找中位數 ——> 尋找兩個合并數組的第 K 大 （K代表中位數）

實現

• ① 遍歷兩個數組 ：通過比較兩個數組的第 [k/2] 個元素 ，如果 numsA[k/2] < numsB[k/2] 的時候，刪除 numsA 的前半部分元素。
• ② 找剩余的 k/2 個元素

---

2- 實現

?4. 尋找兩個正序數組的中位數——題解思路

class Solution {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;return (getKth(nums1,0,n-1,nums2,0,m-1,left)+getKth(nums1,0,n-1,nums2,0,m-1,right))*0.5;}public 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 < len2if(len1>len2) return getKth(nums2,start2,end2,nums1,start1,end1,k);// 1. 遞歸終止條件if(len1 == 0 ) return nums2[start2+k-1];if(k==1) return Math.min(nums1[start1],nums2[start2]);// 2. 遞歸邏輯// 2.1 更新start用于遞歸：保證盡可能不越界 int i = start1 + Math.min(len1,k/2) -1;int j = start2 + Math.min(len2,k/2) -1;// 2.2 刪除邏輯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));}}
}

---

3- ACM 實現

public class midNum {public static double twoNumMid(int[] nums1,int[] nums2){int len1 = nums1.length;int len2 = nums2.length;int left = (len1+len2+1)/2;int right = (len1+len2+2)/2;return (getKth(nums1,0,len1-1,nums2,0,len2-1,left)+getKth(nums1,0,len1-1,nums2,0,len2-1,right))*0.5;}// 遞歸public static int getKth(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){// 找lenint len1 = end1-start1+1;int len2 = end2-start2+1;if(len1>len2) return getKth(nums2,start2,end2,nums1,start1,end1,k);// 2. 終止條件if(len1 == 0) return nums2[start2+k-1];if(k == 1) return Math.min(nums1[start1],nums2[start2]);// 3.單層遞歸int i = start1 + Math.min(k/2,len1)-1;int j = start2 + Math.min(k/2,len2)-1;// 刪 nums2if(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));}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("輸入數組1的長度");int n = sc.nextInt();int[] nums1 = new int[n];System.out.println("輸入數組1元素");for(int i = 0 ; i < n ; i ++){nums1[i] = sc.nextInt();}System.out.println("輸入數組2的長度");int m = sc.nextInt();int[] nums2 = new int[m];System.out.println("輸入數組2元素");for(int j = 0 ; j < m;j++){nums2[j] = sc.nextInt();}double res = twoNumMid(nums1,nums2);System.out.println("中位數是"+res);}
}

---