[LeetCode] 4. 두 개의 질서 있 는 배열 의 중위 수 (특수 한 이분법) 를 찾 습 니 다.
10101 단어 Leetcode
포인트
m + n 의 질서 있 는 배열 이 라면 중위 의 복잡 도 O(1) 를 찾 아 직접 얻 는 length / 2 곳 이 답 이다.한편, 두 개의 질서 있 는 배열 을 하나의 질서 있 는 배열 로 조합 하 는 복잡 도 는 O(m + n) 로 제목 이 요구 하 는 복잡 도 를 초과 했다. K = (n + m) / 2, 즉 중위 수의 번호 로 두 배열 의 K 번 째 큰 수 를 찾 으 면 답 을 찾 을 수 있다.우 리 는 A 와 B 수조 에 한 사람 당 K / 2 개의 숫자 를 줄 기 회 를 주 었 다. Ka
A:----------|---------------
1 2
Kb
B:----------|-------------------------------
3 4
위 에 A 와 B 두 개의 질서 있 는 배열 (작은 것 부터 큰 것 까지) 이 고 세로 선 은
Ka = A[K / 2] 과 Kb = B[K / 2] 이 라 고 가정 한다.이 네 단락 의 길 이 는 각각 L1, L2, L3, L4 이다.Ka 와 Kb 를 비교 하면
Ka > Kb K 는 반드시 Kb 보다 작은 부분, 즉 L3 에 떨 어 지지 않 을 것 이다.그렇다면 L1 + L2 + L4 에서 제 K - L3 개 수 를 찾 는 것 이다.매번 K / 2 단 을 제외 할 수 있 기 때문에 전체적인 복잡 도 는 K = (n + m) / 2 이다.코드
double min(double a,double b){
if(a>b)return b;
return a;
}
double calKth(int a[],int n,int b[],int m,int k){
if(n==0)
return b[k-1];
else if(m==0)
return a[k-1];
if(k==1)
return min(a[0],b[0]);
int ma=min(k/2,n),mb=min(k/2,m);
if(a[ma-1]>b[mb-1]){
return calKth(a,n,b+mb,m-mb,k-mb);
}
return calKth(a+ma,n-ma,b,m,k-ma);
}
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
if((nums1Size+nums2Size)%2){
return calKth(nums1,nums1Size,nums2,nums2Size,(nums1Size+nums2Size+1)/2);
}
int k1=(nums1Size+nums2Size)/2,k2=k1+1;
return (calKth(nums1,nums1Size,nums2,nums2Size,k1)+calKth(nums1,nums1Size,nums2,nums2Size,k2))/2.0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
