[leetcode] 4 - 두 개의 질서 있 는 배열 의 중위 수 를 찾 습 니 다.

m 와 n 크기 의 질서 있 는 배열 을 지정 합 니 다. nums 1 과 nums2。
이 두 질서 있 는 배열 의 중위 수 를 찾 아 알고리즘 의 시간 복잡 도 를 요구 하 십시오. O(log(m + n))。
너 는 가정 할 수 있다. nums1 화해시키다 nums2 동시에 비어 있 지 는 않 습 니 다.
Input: nums1 = [1, 3] nums2 = [2]
Output: 중위 수 는 2.0 입 니 다.
2. 사고방식
1. 외 열 은 배열 이 질서 가 있 기 때문에 외 열 로 두 배열 의 marge 를 다른 배열 help [] 로 만 들 수 있 습 니 다.질서 있 는 배열 help 에서 중위 수 를 찾 는 것 은 간단 한 일이 다.(단점 은 질서 있 는 새 배열 을 만 들 기 위해 서 는 별도의 공간 이 필요 하 다 는 것 이다.)
실제 시간 복잡 도 는 O (m + n) 이 고 공간 복잡 도 는 O (m + n) 이다.
2. 두 바늘 법 은 두 바늘 이 각각 두 배열 의 시작 을 가리킨다 고 정의 한다.배열 총수 num 이 홀수 라면 num / 2 번 째 수 를 찾 습 니 다.만약 총수 가 짝수 라면, 그 두 개 / 2 를 찾 으 십시오. (여 기 는 코드 를 제공 하지 않 습 니 다)
시간 복잡 도 O (m + n), 공간 복잡 도 O (1).
3. 이분법 은 일반적인 시간 복잡 도가 O (logn) 인 알고리즘 을 찾 는데 모두 분 치 사상 (그리고 보통 이분) 을 사용 해 야 한다.두 개의 질서 있 는 배열 은 중위 수 를 구하 고 문 제 는 일반적으로 두 개의 질서 있 는 배열 의 k 번 째 수 를 구하 고 k = (m + n) / 2 시 에 원래 문제 의 해 를 구한다.어떻게 k 번 째 수 를 구 합 니까?각각 첫 번 째 와 두 번 째 배열 의 k / 2 개의 수 a 와 b 를 구 한 다음 에 a 와 b 를 비교 하면 a < b 는 두 번 째 k 수가 a 배열 의 k / 2 개의 수 후반 부 에 있 거나 b 배열 의 k / 2 개의 수 전반 부 에 있 음 을 나타 내 고 문제 규 모 를 절반 으로 줄 인 다음 에 재 귀적 으로 처리 하면 된다.
시간 복잡 도 O (log m + n), 공간 복잡 도 O (1)
원본:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/zhen-zheng-ologmnde-jie-fa-na-xie-shuo-gui-bing-pa/
3. 문제 풀이
외배법

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
       int m=nums1.length;
       int n=nums2.length;
       int i=0;
       int j=0;
       int k=0;
       int[] help=new int[n+m];
       while(i<=m-1&&j<=n-1){
           help[k++]=nums1[i]<=nums2[j]?nums1[i++]:nums2[j++];
       }
       while(i

이분 검색 법

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //      nums       
        if (m == 0) {
            if (n % 2 != 0)
                return 1.0 * nums2[n / 2];
            return (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
        }
        if (n == 0) {
            if (m % 2 != 0)
                return 1.0 * nums1[m / 2];
            return (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0;
        }
        int total = m + n;
        //     ，   total / 2 + 1   
        if ((total & 1) == 1) {
            return find_kth(nums1, 0, nums2, 0, total / 2 + 1);
        }
        //     ，   total / 2     total / 2 + 1      
        return (find_kth(nums1, 0, nums2, 0, total / 2) + find_kth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;

    }

    //  a   b    ， k   
    double find_kth(int[] a, int a_begin, int[] b, int b_begin, int k) {
        // a   b       ，  k          k  
        if (a_begin >= a.length)
            return b[b_begin + k - 1];
        if (b_begin >= b.length)
            return a[a_begin + k - 1];
        //k 1 ，             
        if (k == 1)
            return Math.min(a[a_begin], b[b_begin]);

        int mid_a = Integer.MAX_VALUE;
        int mid_b = Integer.MAX_VALUE;
        //mid_a / mid_b      a  、b     k / 2   
        if (a_begin + k / 2 - 1 < a.length)
            mid_a = a[a_begin + k / 2 - 1];
        if (b_begin + k / 2 - 1 < b.length)
            mid_b = b[b_begin + k / 2 - 1];
        //  a     k / 2     b     k / 2   ，      k      a  k / 2      ，   b   k / 2      
        //        k / 2   ，      k                k - k / 2  ，    
        if (mid_a < mid_b)
            return find_kth(a, a_begin + k / 2, b, b_begin, k - k / 2);
        //    
        return find_kth(a, a_begin, b, b_begin + k / 2, k - k / 2);
    }
}