【LeetCode】#004,2つの秩序配列の中位数を探す
2552 ワード
一、テーマの説明
mとnのサイズの2つの秩序配列nums 1とnums 2が与えられる.この2つの秩序配列の中位数を見つけ,アルゴリズムの時間的複雑さをO(log(m+n))とすることを要求してください.nums 1とnums 2が同時に空にならないと仮定できます.
二、問題を解く
中位数:データのグループの中で中間位置にある数で、サンプル、クラスタ、または確率分布の数値を表します.数値のセットを等しい上下の2つの部分に分割できます.
この問題は本当に難しいですね.アルゴリズムの時間の複雑さはそこに要求されていますから、答えを出せばいいというわけではありません.最適解が必要です.こちらはleetcodeのある大神のスクリーンショットの考え方を参考にして、私の理解を加えて出力をなくしました.
三、ソースコード
四、githubを添付
https://github.com/maryyMa/LeetCodeTest/commit/86bef193c607f6c2ed553118af74d1eb61550852
mとnのサイズの2つの秩序配列nums 1とnums 2が与えられる.この2つの秩序配列の中位数を見つけ,アルゴリズムの時間的複雑さをO(log(m+n))とすることを要求してください.nums 1とnums 2が同時に空にならないと仮定できます.
二、問題を解く
中位数:データのグループの中で中間位置にある数で、サンプル、クラスタ、または確率分布の数値を表します.数値のセットを等しい上下の2つの部分に分割できます.
この問題は本当に難しいですね.アルゴリズムの時間の複雑さはそこに要求されていますから、答えを出せばいいというわけではありません.最適解が必要です.こちらはleetcodeのある大神のスクリーンショットの考え方を参考にして、私の理解を加えて出力をなくしました.
三、ソースコード
public static void main(String[] args) {
int nums1[] = {2, 7, 11, 15};
int nums2[] = {3, 7, 8, 14, 45};
double result = findMedianSortedArrays(nums1, nums2);
System.out.println("result:" + result);
}
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;// 1
int m = nums2.length;// 2
int odd = (n + m + 1) / 2;// ,
int even = (n + m + 2) / 2;// ,
// , , k 。
return (getNth(nums1, 0, n - 1, nums2, 0, m - 1, odd) + getNth(nums1, 0, n - 1, nums2, 0, m - 1, even)) *0.5;
}
/**
* n ,
*
* @param nums1 1
* @param start1
* @param end1
* @param nums2 2
* @param start2
* @param end2
* @param n
* @return
*/
private static int getNth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int n) {
int len1 = end1 - start1 + 1;// 1
int len2 = end2 - start2 + 1;// 2
// len1 len2, , len1
if (len1 > len2) return getNth(nums2, start2, end2, nums1, start1, end1, n);
// 1 , 2 N
if (len1 == 0) return nums2[start2 + n - 1];
// n 1 , ,
if (n == 1) return Math.min(nums1[start1], nums2[start2]);
// ,
int i = start1 + Math.min(len1, n / 2) - 1;
int j = start2 + Math.min(len2, n / 2) - 1;
// 1 i 2 j 。
// 1 i , 2 j , 2 j+1 。
if (nums1[i] > nums2[j]) {
// n , ,n=n- -1。
return getNth(nums1, start1, end1, nums2, j + 1, end2, n - (j - start2 + 1));
}
// 2 j 。
else {
return getNth(nums1, i + 1, end1, nums2, start2, end2, n - (i - start1 + 1));
}
}
}
四、githubを添付
https://github.com/maryyMa/LeetCodeTest/commit/86bef193c607f6c2ed553118af74d1eb61550852