最小的k个数

题目描述

给定一个乱序的整型数组，求这个数组中最小的k个数

解法一

快排序思想，随机取一个数值，然后按大于该数或小于该数分为两部分，然后返回该数在数组中的位置index，判断是否等于k-1；如果等于k-1，则说明此时所求的最小的k个数位于数组前k个；否则根据k的位置继续寻找index=k-1;时间为O(n)，但是会改变原数组；

解法一代码

      vector<int> output;
        int start = 0;
        int 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 {
                end = index - 1;
                index = Partition(&input, start, end);
            }
        }
        for (int i = 0; i < k; i++) {
            output.push_back(input[i]);
        }
        return output;
    }
    
    int Partition(vector<int>* input, int start, int end) {
        int pkey = (*input)[start];
        while (start < end) {
            while (start < end && (*input)[end] >= pkey) end--;
            (*input)[start] = (*input)[end];
            while (start < end && (*input)[start] <= pkey) start++;
            (*input)[end] = (*input)[start];
        }
        (*input)[start] = pkey;
        return start;
    }

解法二

使用堆，遍历数组，设置一个大小为k的容器；初始将数组前k个数字放入容器中，然后后续的数组跟容器中的最大值比较，若小于，则删除最大值放入该值；所以问题在于寻找容器的最大值；遍历就需要O(k)，所以总的是O(kN)，若k为n，则最差为O(N^2);使用堆排序，时间复杂度为O(logk),总的为O(nlogk);使用STL容器set或multiset，会自动对容器内数据排序，时间复杂度为O(logn);

解法二代码

  vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> output;
        if(k<=0 || input.size()==0 || k>input.size()){
            return output;
        }
        int is = input.size();
        multiset<int> s;
        for(int i = 0 ; i < is ; i++ ){
            if(s.size()<k){
                s.insert(input[i]);
                continue;
            }
            set<int>::reverse_iterator riter;
            riter = s.rbegin();
            if((*riter)>input[i]){
                s.erase(*riter);
                s.insert(input[i]);
            }
        }
        set<int>::iterator iter;
        for(iter = s.begin();iter!=s.end();iter++){
            output.push_back(*iter);
        }
        return output;
    }

总结

解法一速度快，但是会动用到原数组；解法二速度虽然没一的快，但是适合于海量数据，因为可以将大量n放到磁盘中，而将容器中的数据放入到内存；