剣指offer最小のK個数C++実現

タイトルの説明:n個の整数を入力して、その中の最小のK個の数を探し出します.例えば4,5,1,6,2,7,3,8の8つの数字を入力すると、最小の4つの数字は1,2,3,4である.
まず,特殊な場合の配列が空であるか,Kが0であるか,Kが配列長より大きいかを考慮する.
次に、どのような方法でソートするかを考えます.
1、C++標準ライブラリsortを使用する

class Solution {
public:
    vector GetLeastNumbers_Solution(vector input, int k) {
         
        vector tmp;
        if(input.empty() || k == 0 || k > input.size()) return tmp;
        sort(input.begin(), input.end());
        tmp.assign(input.begin(), input.begin() + k);
        return tmp;
    }
};

​

標準ライブラリのsort関数のデフォルトは、小さいものから大きいものまでソートされます.大きいものから小さいものへのソートを実現するには、3番目のパラメータgreater()を追加する必要があります.
時間の複雑さを分析しましょう.std::sortは、平均的な場合の線形O(n log n)時間の複雑さを有しなければならない.
2、快速列

class Solution {
public:
    int Partition(vector& v, int low, int high){
        int pivot = v[low];
        while(low < high){
            while(low < high && v[high] >= pivot) high--;
            v[low] = v[high];
            while(low < high && v[low] <= pivot) low++;
            v[high] = v[low];
        }
        v[low] = pivot;
        return low;
    }
    
    void QuickSort(vector& v, int low, int high){
        if(low < high){
            int pivotpos = Partition(v, low, high);
            QuickSort(v, low, pivotpos - 1);
            QuickSort(v, pivotpos + 1, high);
        }
    }
    vector GetLeastNumbers_Solution(vector input, int k) {
        
        vector tmp;
        if(input.empty() || k == 0 || k > input.size()) return tmp;
        QuickSort(input, 0, input.size() - 1);
        tmp.assign(input.begin(), input.begin()+k);
        return tmp;
    }
};

時間複雑度:O(nlog 2 n).