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


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

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 설명

두 개의 정렬된 배열의 중앙값 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