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));
    }
}