在数组中求前K小的元素集合

class Solution {
public:
    //T(n) = O(arr.size() * k)
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        if(arr.size() == 0 || k == 0)   return {};
        int maxIndex = 0;
        for(int i = 1; i < k; i++)
        {
            if(arr[i]>arr[maxIndex])    maxIndex = i;
        }

        for(int i = k; i<arr.size(); i++)
        {
            if(arr[i] < arr[maxIndex])
            {
                arr[maxIndex] = arr[i];

                //重新让maxIndex指向前k小元素中的最大值
                for(int i = 0; i<k; i++)
                {
                    if(arr[i] > arr[maxIndex])  maxIndex = i;
                }
            }
        }

        vector<int> ans(arr.begin(),arr.begin()+k);
        return ans;
    }
};

使用数组前k个元素保存现在前k小的元素。
1.先找出arr数组前k个元素中最大元素的下标maxIndex。
2.从第k+1个元素往后遍历。若元素arr[i]比arr[maxIndex]小，则令arr[maxIndex]=arr[i]，重新在前k个元素中求出最大元素的下标maxIndex。
3.继续往后遍历。

时间复杂度T(n) = O(n * k)，其中n为数组长度。