剑指offer——面试题30：最小的K个数

Solution1:

菜鸟做法，排序后挑选前k个数。复杂度为 $O(nlogn)$

排序可以自己手撸快排代码，或者利用库函数sort()，这里为了省劲就用sort()了。。。

class Solution {public:    vector
   
     GetLeastNumbers_Solution(vector
    
      input, int k) {        vector
     
       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)$ ，这种思路的限制是需要修改输入的数组。

20180904重做。

class Solution {public:    vector
   
     GetLeastNumbers_Solution(vector
    
      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
     
       (input.begin(), input.begin() + k);    }    int Partition(vector
      
        &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
       
         &input, int i, int j) {        int temp = input[i];        input[i] = input[j];        input[j] = temp;        return;    }};

Solution3:

利用最大堆，时间复杂度 $O(nlogk)$ ，特别适合处理海量数据。但最大堆实现起来很麻烦。可以利用C++中的set和multiset，这俩容器是基于红黑树实现，在红黑树中的插入、删除和查找也是只需要 $O(logk)$ 的时间，代码如下：

这个好处是不需要改变原始数组内容。

class Solution {public:    vector
   
     GetLeastNumbers_Solution(vector
    
      input, int k) {        vector
     
       result;        if (input.empty() || k<1 || input.size() < k)            return result;        multiset
      
        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
       
         (insert_set.begin(), insert_set.end());    }};

转载地址：http://pxhdb.baihongyu.com/

你可能感兴趣的文章