시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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, 두 파티션의 왼쪽과 두 파티션의 오른쪽을 더한 부분집합의 길이는 같습니까?
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
