[귀속 카드 2] 두 개의 질서수 그룹의 K 소수를 구하다

[제목]

두 개의 질서수조arr1과arr2를 정하고, 이미 알고 있는 두 개의 수조의 길이는 각각 m1과 m2이며, 두 개의 수조 중의 K소수를 구한다.시간 복잡도 O (log(m1 + m2)가 필요합니다.

[예시]

예를 들어arr1=[1,2,3],arr2=[3,4,5,6],K=4.
K 소수는 3입니다.
예를 들어arr1=[0,1,2],arr2=[3,4,5,7,8],K=3;
K 소수는 2입니다.

【난이도】

어렵다

해답

이 문제는 내가 지난번에 말한 그 문제와 매우 유사하다. 귀속타카드 1: 두 길이가 같은 정렬수 그룹에서 상중위수를 찾았다. 만약 보지 못한 건의를 먼저 보자. 단지 오늘의 이 문제는 지난번의 그 문제보다 조금 어렵고 원리가 같다.
다음은 제가 마음대로 원리를 말씀드리겠습니다. 귀속적인 방법으로 K를 끊임없이 축소하고 K의 작은 원소를 제(K-K/2)작은 원소로 전환시키는...내가 예를 들자, 비교적 이해하기 쉽다.
우리는arr1=[1,2,3],arr2=[3,4,5,6],K=4를 가정한다.
이전 문제와 유사하다(주의: 여기서 우리는 K가 0에서 계산된다고 가정한다. 즉, 0의 작은 원소가 있는데 이는 K=K-1에 해당한다).
mid1 = K/2 = 1.
mid2 = K/2 = 1.
이때arr2[mid2]>arr2[mid1], 문제는 수조arr1[mid1+1...m1]과 수조arr2[0...m2]에서 제(K-md1-1)의 작은 원소를 찾는 것으로 바뀌었다.
그러나 여기서 주의해야 할 것은 k/2의 값이 m1이나 m2보다 클 수 있기 때문에 k/2>m1이나 m2이면 md1=m1-1 또는md2=m2-1로 하면 된다.
코드는 다음과 같습니다.

    //  ， 
    // (（n+m+1)/2+(n+m+2)/2)/2。
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
//        return (findKthNumber(nums1, 0, n-1, nums2,0,m-1,(n+m+1)/2) +
//                findKthNumber(nums1, 0, m-1,nums2,0,m-1,(n+m+2)/2)) /2;
        return 1;
    }

    public static int findKth(int[] arr1, int[] arr2, int k) {
        if(arr1 == null || arr1.length < 1)
            return arr2[k-1];
        if(arr2 == null || arr2.length < 1)
            return arr1[k-1];
        //  7 ， 3 ， 
        return findKth(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k - 1);
    }

    public static int findKth(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2, int k) {
        //  
        if(l1 > r1)
            return arr2[l2 + k];
        if(l2 > r2)
            return arr1[l1 + k];
        if (k == 0)//  ，k == 0 。
            return Math.min(arr1[l1],arr2[l2]);
        int md1 = l1 + k/2 < r1 ? l1 + k/2 : r1;
        int md2 = l2 + k/2 < (r2 - l1) ? l2 + k/2 : r2;
        if(arr1[md1] < arr2[md2])
            return findKth(arr1, md1 + 1, r1, arr2, l2, r2, k - k / 2 - 1);
        else if (arr1[md1] > arr2[md2])
            return findKth(arr1, l1, r1, arr2, md2 + 1, r2, k - k / 2 - 1);
        else
            return arr1[md1];// arr2[md2] ， 。
    }

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

교체해도 돼요?물론 할 수 있지만, 너 자신에게 남겨 두어라.
다음에 나는 또 이 두 문제와 유사한 문제를 하나 더 낼 것이다. 그러나 난이도는 점차 증가한다.모두 세 개의 이런 문제가 있는데, 반드시 스스로 수동으로 코드를 써야 하고, 반드시 스스로 수동으로 코드를 써야 하며, 반드시 스스로 수동으로 코드를 써야 한다.