题解 | #最小的K个数#

比较简单粗暴的解法，先将input数组排序，然后直接返回排序后数组的前k位。关于时间复杂度，由于这里用的是冒泡排序所以时间复杂度为O(n^2+k)，n为input长度。而若使用时间复杂度更低的排序方法，如快速排序，则可以达到O(nlogn+k)。此处空间复杂度则小于题目要求，仅为O(k)。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {  
        vector<int> result;
        if(input.size() == 0){
            return result;
        }
        for(int i = 0;i < input.size()-1;i++){
            for(int j = 0;j < input.size()-1-i;j++){
                if(input.at(j)>input.at(j+1)){
                    int tmp = input.at(j);
                    input.at(j) = input.at(j+1);
                    input.at(j+1) = tmp;
                }
            }
        }
        for(int i = 0;i < k;i++){
            result.push_back(input.at(i));
        }
        return result;
    }
};

最近刚做了一道归并排序的题，为了加深理解，所以回来用归并排序重新写一遍这个题，换汤不换药，核心思路还是对原数组排序后取前k个数。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> temp(input.size());
        vector<int> result;
        if(!input.size() || !k){
            return result;
        }
        merge(input, temp, 0, input.size() - 1);
        for(int i = 0;i < k;i++){
            result.push_back(input.at(i));
        }
        return result;
    }
    void merge(vector<int>& input, vector<int>& temp,int left, int right){
        if(left >= right){
            return;
        }
        int mid = left + (right - left)/2;
        merge(input, temp, left, mid);
        merge(input, temp, mid + 1, right);
        for(int i = left;i <= right;i++){
            temp.at(i) = input.at(i);
        }
        int l = left;
        int r = mid + 1;
        for(int i = left;i <= right;i++){
            if(l == mid + 1){
                input.at(i) = temp.at(r++);
            }
            else if(r == right + 1 || temp.at(l) < temp.at(r)){
                input.at(i) = temp.at(l++);
            }
            else{
                input.at(i) = temp.at(r++);
            }
        }
    }
};

写的时候遇到一个小坑。

if(l == mid + 1){
  first sentence...
}
else if(r == right + 1 || temp.at(l) < temp.at(r)){
  secound sentence...
}
else{
  first sentence...
}
----------------------------------------------------
if(r == right + 1 || temp.at(l) < temp.at(r)){
  first sentence...
}
else{
  secound sentence...
}

在核心交换逻辑中有以上的判断代码，原版是上面的判断逻辑。我在写的时候想，上下两个语句中执行的代码都一样，中间夹了个if else，那直接把这两个执行体一样的判断合在一起做一个else不就行了。
事实证明这样做是不行的，尽管他们执行体一样，但判断逻辑的先后对程序有很大影响。下面哪种写法，只要当左数组数比右数组数小就会直接移动左指针，而并不判断左指针是否越界，所以必须在移动左指针前执行越界判断逻辑。同理，之所以在第二个判断体判断右指针是否越界，是因为第三个判断题要移动右指针。

在对模版代码的逻辑进行优化时，一定要在深思熟虑后在行动，以免因自以为是造成错误。