LeetCode 문제 풀이 노트 (4) 두 정렬 배열 의 중위 수

제목: m 와 n 크기 의 질서 있 는 배열 을 지정 합 니 다. nums1 화해시키다 nums2 。
이 두 질서 있 는 배열 의 중위 수 를 찾 아 보 세 요.요구 알고리즘 의 시간 복잡 도 는 O(log (m+n)) 。
예시 1:
예시 2:

nums1 = [1, 3]
nums2 = [2]

     2.0

해법 1: 문제 가 요구 하 는 시간 복잡 도 를 고려 하지 않 고 두 배열 을 옮 겨 다 니 며 하나의 배열 을 합성 하면 중위 수 를 얻 을 수 있다.

nums1 = [1, 2]
nums2 = [3, 4]

     (2 + 3)/2 = 2.5

두 배열 을 거꾸로 옮 겨 다 니 며 비교 한 후 결과 배열 에 순서대로 넣 고 질서 있 는 총 배열 을 얻 은 다음 에 중위 로 돌아 가 는 것 이 중간 두 수의 평균 수 를 취 하 는 것 이다.
시간 복잡 도: O (m + n)
공간 복잡 도: O (m + n)
해법 2: 문 제 는 O (log (m + n) 의 시간 복잡 도 를 요구 합 니 다. 일반적으로 분 치 법 이나 2 분 검색 입 니 다.먼저 우 리 는 먼저 문 제 를 분석 하고 두 개의 질서 있 는 서열 이 모두 n 개의 요소 (중위 수의 정의 에 따라 우 리 는 두 가지 상황 으로 나 누 어 고려 해 야 한다) 가 있다 고 가정 한다. n 이 홀수 일 때 제 (n / 2 + 1) 요 소 를 찾 고 n 이 짝수 일 때 제 (n / 2 + 1) 와 제 (n / 2) 요 소 를 찾 은 다음 에 그들의 평균 값 을 취한 다.
가설 서열 은 모두 작은 것 에서 큰 것 으로 배열 되 어 있다. 첫 번 째 서열 에서 앞의 p 개 요소 와 두 번 째 서열 에서 앞의 q 개 요소 에 대해 우리 가 원 하 는 최종 결 과 는 p + q 는 k - 1 과 같 고 한 서열 의 두 번 째 p 개 요소 와 두 번 째 서열 의 두 번 째 q 개 요 소 는 모두 전체 서열 의 k 번 째 요소 보다 작다.전체 서열 에서 반드시 k - 1 개의 요소 가 k 번 째 요소 보다 작 기 때문이다.이렇게 하면 p + 1 개의 요소 나 q + 1 개의 요 소 는 우리 가 찾 는 k 번 째 요소 입 니 다.따라서 우 리 는 이분법 을 통 해 문제 의 규 모 를 축소 할 수 있다. p = k / 2 - 1 을 가정 하면 q = k - p - 1 이 고 p + q = k - 1 이다.만약 에 첫 번 째 서열 의 p 번 째 요소 가 두 번 째 서열 의 q 번 째 요소 보다 작다 면 우 리 는 두 번 째 서열 의 q 번 째 요소 가 큰 지 작은 지 확실 하지 않 지만 한 서열 의 앞 p 번 째 요 소 는 목표 보다 작 을 것 이다. 그래서 우 리 는 첫 번 째 서열 의 앞 p 번 째 요 소 를 모두 버 리 고 비교적 짧 은 새로운 서열 을 형성 할 것 이다.그 다음 에 새로운 서열 로 원래 의 첫 번 째 서열 을 대체 한 다음 에 그 중의 k - p 요 소 를 찾 습 니 다 (우 리 는 p 개의 요 소 를 배 제 했 기 때문에 k 는 k - p 로 업데이트 해 야 합 니 다). 순서대로 재 귀 합 니 다.마찬가지 로 첫 번 째 서열 의 p 번 째 요소 가 두 번 째 서열 의 q 번 째 요소 보다 크 면 우 리 는 두 번 째 서열 의 앞 q 번 째 요 소 를 포기 합 니 다.귀환 의 중지 조건 은 다음 과 같은 몇 가지 가 있다.           1. 비교적 짧 은 서열 의 모든 요소 가 버 려 지면 비교적 긴 서열 의 k 번 째 요 소 를 되 돌려 줍 니 다 (배열 에서 아래 표 시 는 k - 1)           2. 1 서열 의 p 번 째 요 소 는 2 서열 의 q 번 째 요소 와 같 습 니 다. 이때 전체 서열 의 p + q = k - 1 번 요소 의 다음 요소, 즉 전체 서열 의 k 번 째 요소 입 니 다.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;         //    1             
        int n = nums2.length;         //  2   
        int length = m + n;           //       
        int[] result = new int[length];      //       
        for(int i = length-1;i>=0;i--){      //  length-1 
             int num1 = m-1>=0?nums1[m-1]:Integer.MIN_VALUE;       //    0       ，         
             int num2 = n-1>=0?nums2[n-1]:Integer.MIN_VALUE;
             if(num1>num2){
                 result[i] = num1;                                //                  ，
                 m--;                                             //    
             }else {
                 result[i] = num2;
                 n--;
             }
        }
        return (result[length/2]+result[(length-1)/2])/2.0;      //     
    }
}