Leetcode 문제풀이 4.Median of Two Sorted Arrays

Leetcode 문제

4.Median of Two Sorted Arrays-Hard

Author: Zinc 키워드: 분할, 귀속, 2분

제목

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

중국어 약술

두 개의 질서수 그룹인nums1과nums2가 있는데 길이는 각각 n과 m로 두 그룹이 합쳐진 중위수를 찾아낸다.특별 요구사항: 시간 복잡도 O(log(m+n)

분석

선형 시간: 제목을 보면 누군가가 말하기 시작한다. 이 문제는 간단하잖아. 두 개의 질서수 그룹을 하나의 질서수 그룹으로 통합한 다음에 중위수의 정의를 사용한다. 중위수는 질서수 그룹의 중간에 있는 그 수(길이가 홀수)나 중간 두 개의 수의 평균수(길이가 짝수일 때)이다.원래 주어진 두 개의 수조는 이미 질서정연한 수조이기 때문에 우리는 병합 정렬의 조작과 같이 한 걸음만 하면 된다. 시간의 복잡도는 m+n이고 선형으로 한 번씩 차례를 배열하면 된다.마지막으로 공식으로 전체 단계는 m+n+1걸음이고 시간 복잡도는 O(m+n)이다. 선형의 시간은 이미 우수한 것 같아서 제목은 완벽한 마침표를 그린다."야야야, 너 눈 멀었어... 제목이 log(m+n)의 시간을 쓰라고 했구나!"(퀴즈를 맞힐 때 옆에서 조롱이 들려온다)"뭐야! 야옹? 야옹? 야옹?"(이때의 내 얼굴은 흑인 물음표), 눈을 똑바로 뜨고 보니 정말log(m+n), 하늘이 누구를 돌아다녔는지.역시 이 하드의 제목은 만만한 것이 아니다.
대수 시간 분석: 대수 시간을 보면 많은 사람들이 나와 같다고 믿는다. 처음에는 어리둥절했는데 어떻게 하지?사실 시간을 세는 점에 대해 말하자면 이렇게 빠른 알고리즘에 도달할 수 있는 것은 많지 않고 가장 흔히 볼 수 있는 것은 이분의 사상이다.자, 2분을 절입점으로 아래로 확장한다. 이른바 중위수를 찾는 것은 사실 제2k=len/2(상향으로 정돈)의 수나 k=len/2와 k=len/2+1의 두 수의 평균수를 찾는 것이다. 문제는 2개의 질서수 그룹 중 두 번째로 큰 숫자를 찾는 것으로 바뀌었고 2분을 통해 두 개의 수조의 규모를 줄인다.우리가 문제를 풀 수 있는 코드를 얻었다.간단한 절차는 다음과 같다.좌우 양쪽에서 두 번째로 큰 K를 찾습니다.각각 두 개의 수조 k/2 위치의 숫자를 찾아 비교한다. 만약에 a1[k/2]>a2[k/2]가 설명하면 a1 전 k/2는 수소 범위 밖에 있고 반대로 a2의 전 k/2이다.(k/2의 길이와 a1의 길이를 최소화하는 알고리즘; a1이 숫자가 없으면 답이 b에 있고 같으면 답이 같은 숫자이다.)삼.상황1은 a1을 전 k/2를 제거하고 두 개의 수조 중 k/2가 큰 숫자를 검색합니다. 상황2는 a2가 전 k/2를 제거하고 두 개의 수조 중 k/2가 큰 숫자를 검색합니다.

Source Code

1. 합병

    class Solution {
    public:
        double med_singlevec(vector<int>& nums){
            int len = nums.size();
            int mid = len/2;
            return ((len%2==0)? ((nums[mid]+nums[mid-1])/2.0) : nums[mid]);
        }

        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int i = 0, j = 0;
            vector<int> nums;
            for(i = 0, j = 0; i<nums1.size()&&j<nums2.size();){
                if(nums1[i]<=nums2[j]){
                    nums.push_back(nums1[i++]);
                }
                else
                    nums.push_back(nums2[j++]);
            }
            while(i<nums1.size())
                nums.push_back(nums1[i++]);
            while(j<nums2.size())
                nums.push_back(nums2[j++]);
            return  med_singlevec(nums) ;


        }

2.2분치

    #include <cmath>
    class Solution {
    public:
        double findKthnum(vector<int>&a, vector<int>&b, int k){
            int alen = a.size(), blen = b.size();
            if(alen > blen)
                return findKthnum(b, a, k);
            if(alen==0)
                return b[k-1];
            if(k==1)
                return min(a[0],b[0]);
            int pa = min(k/2, alen);
            int pb = k - pa;
            if(a[pa-1] < b[pb-1]){
                vector<int>*na = new vector<int>(a.begin()+pa, a.begin()+alen);
                return findKthnum(*na,b,k-pa);
            }

            else if(a[pa-1] > b[pb-1]){
                vector<int>* nb = new vector<int>(b.begin()+pb,b.begin()+blen);
                return findKthnum(a,*nb,k-pb);
            }

            else
                return a[pa-1];

        }
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int total = nums1.size()+nums2.size();
            if(total % 2 == 1){
                return findKthnum(nums1, nums2, total/2 +1);
            }
            else{
                return (findKthnum(nums1, nums2, total/2)+
                        findKthnum(nums1, nums2, total/2+1))/2.0;
            }
        }
    };