두 개의 정렬된 배열의 중앙값 LeetCode 솔루션


자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 Facebook 골드만 삭스 구글 Microsoft 신탁 웨이 페어 Yahoo
리트코드 LeetCodeSolutions 감독자조회수 71

문제 설명

두 개의 정렬된 배열의 중앙값 LeetCode 솔루션 – "두 개의 정렬된 배열의 중앙값" 문제에서 두 개의 정렬된 배열이 제공됩니다. nums1 및 nums2 크기 m 및 n 각각, 그리고 우리는 반환해야 중앙값 두 개의 정렬된 배열 중

전체 런타임 복잡성은 다음과 같아야 합니다. O(log (m+n)).

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

설명 : 병합된 배열 = [1,2,3]이고 중앙값은 2입니다.

접근

이 문제를 해결하려면 먼저 중앙값이 실제로 무엇을하는지 이해해야합니다.

하나의 서브 세트가 다른 서브 세트보다 크도록 세트를 두 개의 동일한 길이 서브 세트로 분할하는 것입니다.

즉, 집합을 두 개의 부분 집합으로 분할하여 모든 한 부분집합의 요소가 더 큼 다른 하위 집합의 모든 요소보다

이제 문제로 돌아가서 다음을 찾아야 합니다. 정렬된 두 배열의 중앙값.

찾을 수 있을까요? 어레이용 파티션 A와 B, 두 파티션의 왼쪽과 두 파티션의 오른쪽을 더한 부분집합의 길이는 같습니까?

두 개의 정렬된 배열의 중앙값 LeetCode 솔루션

i 번째 위치에서 배열을 분할하는 것은 왼쪽 부분 집합에있는 해당 배열의 요소 수를 나타냅니다.

그리고 우리가 알고 있듯이 얻은 하위 집합은 같아야 합니다., 따라서 파티션A + 파티션B = (길이(A) + 길이(B)+1)/2

(최종 길이의 경우 병합 정렬 배열이 홀수이면 왼쪽 하위 집합에 더 많은 요소가 있습니다)

이제 남은 것은 오른쪽 하위 집합이 왼쪽 하위 집합보다 크도록 주어진 두 배열을 분할하는 방법을 확인하는 것입니다.

의 완벽한 분할을 정의합시다. 정렬된 배열:

배열 A (길이 n)와 배열 B (길이 m)가 있다고 가정 해 보겠습니다.

우리는 i에서 A와 j에서 B를 분할했습니다.

완벽한 파티션은 다음과 같은 경우입니다.

  • i + j = (n + m + 1) / 2 (부분 집합의 길이가 같음)
  • A [i-1] <= B [j] (i의 왼쪽에있는 A의 요소가 왼쪽 부분 집합에 포함됨)
  • B [j-1] <= A [i] (j의 왼쪽에있는 B의 요소는 왼쪽 부분 집합이됩니다)

A [i-1]> B [j]이면 A의 파티션 왼쪽에 더 큰 (오른쪽) 하위 집합에 배치되어야하는 일부 요소가 있음을 의미합니다. 이 경우 i를 왼쪽으로, j를 오른쪽으로 이동합니다.

B [j-1]> A [i]이면 B의 파티션 왼쪽에 더 큰 (오른쪽) 하위 집합에 배치해야하는 요소가 있다는 의미입니다. 이 경우 j를 왼쪽으로, i를 오른쪽으로 이동합니다.

암호

정렬된 두 배열의 중앙값에 대한 C++ 코드

#include <bits/stdc++.h>
using namespace std;

double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    long n = A.size(), m = B.size(), t=(n+m+1)/2;
    if(n>m)return findMedianSortedArrays(B,A);
    if(n==0) return m % 2 == 0 ? (double)(B[m/2 - 1] + B[m/2]) / 2 : B[m/2];
    if(m==0) return n % 2 == 0 ? (double)(A[n/2 - 1] + A[n/2]) / 2 : A[n/2];
    long left = 0, right = n;
    while (left <= right) {
        long partitionA = left + (right-left)/2;
        long partitionB = t - double(partitionA);      // partitionA + partitionB = (n+m+1)/2
        //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
        double maxLeftA = INT_MIN;
        if(partitionA > 0){
            maxLeftA = A[partitionA-1];
        }
            
        //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
        double minRightA = INT_MAX;
        if(partitionA < n){
            minRightA = A[partitionA];
        }
        
        //Similarly for maxLeftB and minrightB
        double maxLeftB = INT_MIN;
        if(partitionB > 0){
            maxLeftB = B[partitionB-1];
        }
            
        double minRightB = INT_MAX;
        if(partitionB < m){
            minRightB = B[partitionB];
        }
        if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
            if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB))/2.0;
            } 
            else {
                return max(maxLeftA, maxLeftB);
            }
        } 
        else if (maxLeftA > minRightB) {                          //move left side.
            right = partitionA - 1;
        }
        else {                                                   // move right side
            left = partitionA + 1;
        }
    }
    return 0.0;    // we can't find the median if input is invalid i.e., arrays are not sorted
}
    
    
int main() {
  vector<int> A = {1, 2, 3, 5, 6};
  vector<int> B = {4};
  cout<<findMedianSortedArrays(A, B);
  return 0;
}
3.50000

정렬된 두 배열의 중앙값에 대한 Java 코드

import java.util.Scanner;
public class Main{
    public static double findMedianSortedArrays(int A[], int B[]) {
        int n = A.length, m = B.length;
        if(n>m)return findMedianSortedArrays(B,A);
        int left = 0, right = n;
        while (left <= right) {
            int partitionA = (left + right)/2;
            int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2
            //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
            double maxLeftA = Integer.MIN_VALUE;
            if(partitionA > 0){
                maxLeftA = A[partitionA-1];
            }
                
            //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
            double minRightA = Integer.MAX_VALUE;
            if(partitionA < n){
                minRightA = A[partitionA];
            }
                
            //Similarly for maxLeftB and minrightB
            double maxLeftB = Integer.MIN_VALUE;
            if(partitionB > 0){
                maxLeftB = B[partitionB-1];
            }
                    
            double minRightB = Integer.MAX_VALUE;
            if(partitionB < m){
                minRightB = B[partitionB];
            }
            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
                if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                    return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB))/2.0;
                } 
                else {
                    return Math.max(maxLeftA, maxLeftB);
                }
            } 
            else if (maxLeftA > minRightB) {                          //move left side.
                right = partitionA - 1;
            }
            else {                                                   // move right side
                left = partitionA + 1;
            }
        }
        return 0.0;    // we can't find the median if input is invalid i.e., arrays are not sorted
    }
        
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int A[]=new int[]{1,2,6,8};
        int B[]=new int[]{5,7,10};
        double median = findMedianSortedArrays(A,B);
        System.out.println(median);  
    }
}
6.000

정렬된 두 배열의 중앙값에 대한 복잡성 분석 LeetCode 솔루션

시간 복잡성 : O (로그 (n))

모든 단계에서와 마찬가지로 검색 공간을 절반으로 줄입니다 (중간 인덱스에서 왼쪽 검색 공간 또는 오른쪽 검색 공간 선택).

공간 복잡성 : O (1) 

계산에 몇 가지 변수를 사용하기 때문입니다.

두 개의 정렬된 배열의 중앙값 LeetCode 솔루션을 읽어주셔서 감사합니다!!

참조 – https://en.wikipedia.org/wiki/Array_data_structure

코멘트를 남겨

Translate »
1