package arrays;

/**
 * 题目:寻找两个有序数组的中位数,要求时间复杂度为log
 *
 * @Author Gavin
 * @date 2021年12月21日 21:29
 */
public class array_6 {
 /**
 * 解题思路:
 * 由于要求时间复杂度为log,所以考虑使用二分法进行处理
 * 题目是求中位数,其实就是求第 k 小数的一种特殊情况
 */
 public static double solution(int[] nums1,int[] nums2){
 int length1 = nums1.length, length2 = nums2.length;
 int totalLength = length1 + length2;
 if (totalLength % 2 == 1) {
 int midIndex = totalLength / 2;
 //如果是奇数那么就找中间的第 midIndex+1 个数就是
 return getKthElement(nums1, nums2, midIndex + 1);
 } else {
 int midIndex1 = totalLength / 2, midIndex2 = totalLength / 2+1;
 //如果是偶数那么就计算中间两个数的平均值(也是找到这两个值,然后再求平均值)
 return (getKthElement(nums1, nums2, midIndex1) + getKthElement(nums1, nums2, midIndex2)) / 2.0;
 }
 }

 /**
 * 使用二分法求第K大的数
 * 巧妙
 */
 //Time:O(log(m+n))
 public static int getKthElement(int[] nums1, int[] nums2, int k) {
 int len1 = nums1.length, len2 = nums2.length;
 int base1 = 0, base2 = 0;

 while (true) {
 // 边界情况
 //这里就是数组1的数字都遍历完了还没有找到第k大的,此时说明这个值就直接在第二个数组里面了
 if (len1 == 0) {
 return nums2[base2 + k - 1];//数组是从0开始的,所以需要-1
 }
 if (len2 == 0) {
 return nums1[base1 + k - 1];
 }
 //k=1说明就是找两个数组头指针指向的数字哪个小就是哪个
 if (k == 1) {
 return Math.min(nums1[base1], nums2[base2]);
 }

 //k到这里的值是不可能小于2的。
 int i=Math.min(k/2,len1);//len1表示数组剩下还能够进行判断的元素个数
 int j=Math.min(k-i,len2);
 //i,j得到都是个数,所以下面取下标的时候都要减去一个1定位到数组中位置
 int a=nums1[base1+i-1],b=nums2[base2+j-1];
 if(i+j==k&&a==b)return a;

 if(a<=b){//排除k/2个数
 base1+=i;
 len1-=i;//排除元素后剩下还能继续处理的元素的个数
 k-=i;
 }
 if(a>=b){
 base2+=j;
 len2-=j;
 k-=j;
 }
 }
 }


 /**
 * 两个有序数组求中位数O(m+n)复杂度的例子,也可以用来求第K大的数
 */
 public static double findMedianSortedArrays(int[] A, int[] B) {
 int m = A.length;
 int n = B.length;
 int len = m + n;
 int left = -1, right = -1;
 int aStart = 0, bStart = 0;
 for (int i = 0; i <= len / 2; i++) {
 left = right;
 if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
 right = A[aStart++];
 } else {
 right = B[bStart++];
 }
 }
 if ((len & 1) == 0)
 return (left + right) / 2.0;
 else
 return right;
 }

 public static void main(String[] args) {
 int[] arr1={1,3,5};
 int[] arr2={2,4,6};
 System.out.println(solution(arr1,arr2));
 }
}