Leetcode 분치법

분치법

분치법의 사상은 문제를 분치한다.문제를 작은 문제로 나누다2.분치가 끝난 후, 귀속 중의 종료 판정 문장을 촉발한다.분치의 결과를 한데 합치다

majority 를 구하다

제목

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

해석

majority는 수조에서 n/2회보다 크기 때문에 수조를 반으로 나누어 왼쪽 부분의 대다수와 오른쪽 부분의 대다수를 구할 수 있다. 그러면 문제를 나누어 해결할 수 있다.
merge 부분에서 수조는 그 횟수가 아니라 대부분의 원소만 되돌릴 수 있기 때문에 merge는 두 개의 횟수를 비교하고 비교적 큰 것을 되돌려야 한다.

소스 코드

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        /* 
             left   right ， me
             ， 
            */
        return majorCompute(nums, 0, nums.size() - 1);
    }

    int majorCompute(vector<int>& nums, int left, int right) {
        if (left >= right)
            return nums[left];
        int mid = (left + right) / 2;
        int l = majorCompute(nums, left, mid);
        int r = majorCompute(nums, mid + 1, right);
        if (l == r)
            return l;
        else 
            return count(nums.begin() + left, nums.begin() + mid, l) > count(nums.begin() + mid, nums.begin() + right, r)?  l:  r;
    }

};

큰 수를 구하다

제목

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given [3,2,1,5,6,4] and k = 2, return 5.

해석

이 문제는 가장 좋은 정렬 방법을 사용한다면 시간 복잡도는 O(nlogn)에 도달할 수 있다. 예를 들어 정렬을 쌓는 것이다.
그러나 k대 문제는 전형적인 분치 사상을 운용하여 해결할 수 있는 문제이다.

무작위로 수조에서 하나의 수를 v로 추출하여 원수조를 세 부분으로 나누어 v(Sl)보다 작고 v(Sv)와 같고 v(Sg)보다 크다

만약에 구한 k값이 |Sg|보다 크면 요구하는 값은 반드시 Sg에 있지 않습니다.만약 구한 k값이 |Sg|+|Sv|보다 크다면, 구한 k의 크기는 반드시 Sv에 있지 않을 것이다.나머지 상황은 크면 Sl에서만.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if (nums.size() == 1)
            return nums[0];
        vector<int> Sl, Sv, Sg;
        // v
        int v = nums[nums.size() / 2];
        // 
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == v)
                Sv.push_back(nums[i]);
            else if (nums[i] < v)
                Sl.push_back(nums[i]);
            else 
                Sg.push_back(nums[i]);
        }
        if (k <= Sg.size())
            return findKthLargest(Sg, k);
        else if (k <= Sg.size() + Sv.size())
            return v;
        else 
            return findKthLargest(Sl, k - Sg.size() - Sv.size());


        // sort(nums.begin(), nums.end());
        // return nums[nums.size() - k];
    }
};