精华内容
参与话题
问答
  • 最小的K个数

    2017-04-18 23:10:13
    输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 package algorithm.offer;import java.util.ArrayList;/** * Created by Administrator on 2017/4/18. */ ...

    题目描述
    输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

    package algorithm.offer;
    
    import java.util.ArrayList;
    
    /**
     * Created by Administrator on 2017/4/18.
     */
    public class Solution34 {
        public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input,int k){
            for (int i=0;i<input.length-1;i++){   //直接选择排序总共要经过n-1趟排序
                int min = i;
                for (int j = i+1;j<input.length;j++){
                    if (input[j] < input[min]){
                        min = j;
                    }
                }
                if (min != i){
                    swap(input,i,min);
                }
                System.out.println("第"+(i+1)+"趟 ");
            }
            ArrayList<Integer> arrayList = new ArrayList<Integer>();
            for (int f = 0;f < k;f++){
                arrayList.add(input[f]);
            }
            return arrayList;
        }
        public static void swap(int[] input,int i,int j){
            int temp = input[j];
            input[j] = input[i];
            input[i] = temp;
        }
        public static void main(String args[]){
            int[] array = {4,5,1,6,2,7,3,8};
            int k =4;
            System.out.println("最小的"+k+"个数是:"+GetLeastNumbers_Solution(array,k));
        }
    }
    
    展开全文
  • 最小的k个数

    2019-04-07 23:20:22
    最小的k个数 题目描述 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 解题思路 为了只遍历一次数组,很容易想到用最小堆来存放最小的k个数 因为set是用红黑树...

    最小的k个数

    题目描述

    输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

    解题思路

    • 如果允许修改数组,可使用快速排序中的Partition函数,找到第k个数字,这样他左边的就是我们要的。但是不支持海量数据,因为要把所有数字都读入内存。
    • 借用STL中的set模拟堆,因为set内部使用红黑树实现,自动有序、去重。把当前最小的k个数存入set,不断的用新的数字去比对,决定是否替换set中的最后一个数字
    • 优点:复杂度是O(nlogk),适合海量数据的输入,即不需要把数据都读入内存,可以每次从磁盘中读入一些数,最小只需要内存能容纳k个数就行,适合于n很大,k较小的问题
    • 如果set的容量还没有达到k,直接向里面push
    • 否则,判断当前元素和set最后一个元素(也就是其中最大的数),如果比set中最大的元素小,那么删除最后一个元素,把当前元素push,最后遍历完数组,set中存放的就是最小的k个数
    class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
            vector<int>ans;
            if(k<=0 || k>input.size()||input.empty()) return ans;
            int len=input.size();
            for(int i=0;i<len;i++){
                if(s.size()<k){
                    s.insert(input[i]);
                }else{
                    auto it=s.end();
                    it--;
                    if(input[i]<*(it)){
                        s.erase(it);
                        s.insert(input[i]);
                    }
                }
            }
            for(auto it=s.begin();it!=s.end();it++){
                ans.push_back(*it);
            }
            return ans;
        }
    private:
        set<int>s;
    };
    
    展开全文
  • 最小的 K 个数

    2018-10-02 20:58:39
    输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。 时间限制:1秒 空间限制:32768K 思路一:先进行排序,使序列有序,再取出对应的 K 位,时间复杂度O(nlogn)。 ...

    题目描述

         输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。

    时间限制:1秒

    空间限制:32768K

    思路一:先进行排序,使序列有序,再取出对应的 K 位,时间复杂度O(nlogn)。

    思路二:TOP K 系列问题是数据结构堆的经典应用,堆是一种完全二叉树,最大堆:堆顶元素是堆中最大的;最小堆:堆顶元素是堆中最小的元素。本题中选用最大堆来处理,先将序列中前 K 个元素放入堆中,然后遍历序列中后续元素依次与堆顶元素比较,如果当前元素小于堆顶元素那么将当前元素加入到堆中,并移除堆顶元素即可。

    排序方法代码

    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        int len = input.size();
        if (len == 0 || k > len) return res;
        int a[len];
        for (int i = 0;i < len;i++)
            a[i] = input[i];
        sort(a,a+len);
        for (int i = 0;i < k;i++)
            res.push_back(a[i]);
        return res;
    }
    
    

    堆方法代码

    
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> res = new ArrayList<Integer>();
            int len = input.length;
            if (len < k || k == 0) return res;
            //创建一个容量为 K 的优先队列(堆)
            PriorityQueue<Integer> maxHead = new PriorityQueue<Integer>(k, (o1,o2) -> {return o2.compareTo(o1);});
            for (int i = 0;i < len;i++) {
                if (i < k) {
                    maxHead.add(input[i]);
                } else if (maxHead.peek() > input[i]) {
                    maxHead.poll();//移除堆顶元素
                    maxHead.add(input[i]);
                }
            }
            while (!maxHead.isEmpty()) {
                res.add(maxHead.remove());
            }
            return res;
       }
    
    
    
    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 13,338
精华内容 5,335
关键字:

最小的k个数