검지offer--면접문제 30:최소 K개수

검지offer--면접문제 30:최소 K개수

Solution1:

채소 새를 만드는 방법, 순서를 정한 후 앞의 k개 수를 선택한다.복잡도는 O(nlogn) O(n l o g n) 정렬로 코드를 손쉽게 배열하거나 라이브러리 함수sort()를 이용하면 힘을 아끼기 위해sort()를 사용합니다.

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        int n = input.size();
        if (n < k) return res;
        else {
            sort(input.begin(),input.end());
            for(int i = 0; i < k; i++)
                res.push_back(input[i]);
            return res;
        }
    }
};

Solution2:

빠른 배열에서Partition() 함수를 이용하여 시간 복잡도 O(n)O(n)를 계산하는데 이런 사고방식의 제한은 입력을 수정해야 하는 수조이다.20180904 재작업.

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if (!k || k < 0 || input.size() < k) return {};
        int start = 0, end = input.size() - 1;
        int index = Partition(input, start, end);
        while (index != k - 1) {
            if (index < k - 1) {
                start = index + 1;
                index = Partition(input, start, end);
            } else if (index > k - 1) {
                end = index - 1;
                index = Partition(input, start, end);
            }
        }
        return vector<int> (input.begin(), input.begin() + k);
    }

    int Partition(vector<int> &input, int begin, int end) {
        if (begin >= end) return begin;
        int refer = input[end];
        int tail = begin; //tail      
        for (int i = begin; i < end; i++) {
            if (input[i] <= refer)
                my_swap(input, i, tail++);
        }
        my_swap(input, tail, end);
        return tail;
    }

    void my_swap(vector<int> &input, int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
        return;
    }
};

Solution3:

최대 무더기, 시간 복잡도 O(nlogk) O(nl o g k)를 이용하여 대량의 데이터를 처리하기에 특히 적합하다.하지만 최대 무더기가 실현되기는 귀찮다.C++의 set과 multiset을 이용할 수 있다. 이 두 용기는 붉은색과 검은색 트리를 바탕으로 이루어진 것이다. 붉은색과 검은색 트리에 삽입, 삭제, 검색하는 것도 O(logk) O(l o g k)만 있으면 된다. 코드는 다음과 같다. 이 장점은 원시 그룹의 내용을 바꿀 필요가 없다는 것이다.

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;
        if (input.empty() || k<1 || input.size() < k)
            return result;
        multiset<int> insert_set;//              
        for (int i = 0; i < input.size(); i++) {
            if (i < k) {
                insert_set.insert(input[i]);
            } else {
                auto rit = insert_set.rbegin();
                if (input[i] < *rit){
                    insert_set.erase(*rit);
                    insert_set.insert(input[i]);
                }
            }
        }
        return vector<int> (insert_set.begin(), insert_set.end());
    }
};