/**
* 4. 寻找两个正序数组的中位数
* 给定两个大小别离为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。*
* 算法的工夫复杂度应该为 O(log (m+n))
*
*/
public class Median {public static double findMedianElement(int[] numArray1, int[] numArray2) {
int length1 = numArray1.length, length2 = numArray2.length;
int totalLength = length1 + length2;
// 奇数
if (totalLength % 2 == 1) {
int midIndex = totalLength / 2;
double median = getElement(numArray1, numArray2, midIndex + 1);
return median;
} else {
// 偶数
int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
int k1 = getElement(numArray1, numArray2, midIndex1 + 1);
int k2 = getElement(numArray1, numArray2, midIndex2 + 1);
double median = (k1 + k2) / 2.0;
return median;
}
}
public static int getElement(int[] numArray1, int[] numArray2, int k) {
int length1 = numArray1.length, length2 = numArray2.length;
int index1 = 0, index2 = 0;
// 长期存储 K
int kTemp = k;
// 记录遍历次数
int count = 0;
while (true) {
// 非凡状况，取第一个元素
if (k == 1) {if (length1 == 0){return numArray2[index2];
}
if (length2 == 0){return numArray1[index1];
}
return Math.min(numArray1[index1], numArray2[index2]);
}
// 元素初始值
int pivot1 = -99999, pivot2 = -99999;
// 数组 1，下标没有越界，且数组个数大于 0
if (index1 <= length1 -1 && length1 > 0){pivot1 = numArray1[index1];
}
// 数组 2，下标没有越界，且数组个数大于 0
if (index2 <= length2 -1 && length2 > 0){pivot2 = numArray2[index2];
}
// 曾经遍历了 k- 1 次 等同于 曾经找到了指标元素
if(count == (kTemp-1)){if (index1 > length1 - 1) {return pivot2;}
if (index2 > length2 - 1) {return pivot1;}
return Math.min(pivot1,pivot2);
}
// 谁的元素小，谁挪动指针
if ((pivot1 != -99999 && pivot2 != -99999 && pivot1 <= pivot2) ||
pivot2 == -99999
) {
// 右移 nums1 指针
index1 += 1;
// 记录遍历次数
count += 1;
} else {
// 右移 nums2 指针
index2 += 1;
// 记录遍历次数
count += 1;
}
}
}