栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

最小的k个数

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

最小的k个数

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

第一种方法:
使用sort 然后取前k个数
但是这种方法时间和空间复杂度太高,面试可能会Pass掉。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] a=new int[k];
        Arrays.sort(arr);
        for(int i=0;i
            a[i]=arr[i];
        }
        return a;
    }
}

时间O(n log n),空间 O(log n)
第二种方法:堆
用一个大根堆实时维护数组的前k小值,首先将前k个数插入到大根堆中,随后从第k+1个数开始遍历,如果当前遍历的数比大根堆的堆顶小,就把堆顶的元素弹出,再插入当前遍历到的数,最后将大根堆里的数存入数组返回即可。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] a=new int[k];
        if(k==0 ) return a;
        //定义一个大根堆
        PriorityQueue queue=new PriorityQueue(new Comparator(){
            public int compare(Integer num1,Integer num2){
                return num2-num1;
            }
        });
        //将前k个元素添加到大根堆中
        for(int i=0;i
            queue.offer(arr[i]);
        }
        //将k+1后个元素添加大大根堆中,添加时需要更堆顶元素进行比较
        //新添加的元素比堆顶元素小,则直接将堆顶元素弹出,将新添加的元素加进去
        //新添加的元素比栈顶元素大时,就不添加
        for(int i=k;i
            if(queue.peek()>arr[i]){
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        //将最终堆中还剩下的k个元素放到数组a中,最后返回a
        for(int i=0;i
            a[i]=queue.poll();
        }
        return a;
    }
}

时间复杂度:O(n log k) ,其中n是数组arr的长度,大根堆需要实时维护前K小值,所以插入删除都是O(log k)
空间复杂度:O(k) 大根堆中最多k个数
大根堆:
就是父节点都比子节点大
小根堆:
父节点都比子节点小

PriorityQueue 默认是小根堆

   PriorityQueue queue=new PriorityQueue();

PriorityQueue 实现大根堆需要自定义的comparator,使用o2-o1

        PriorityQueue queue=new PriorityQueue(new Comparator(){
            public int compare(Integer num1,Integer num2){
                return num2-num1;
            }
        });

第三种方法:使用快速排序思想
快速排序的划分函数每次执行完后都能将数组分为两个部分,小于等于分界值的元素都会被放在数组的左边,大于的都会别放在数组的右边。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        randomizedSelected(arr, 0, arr.length - 1, k);
        int[] vec = new int[k];
        for (int i = 0; i < k; ++i) {
            vec[i] = arr[i];
        }
        return vec;
    }

    private void randomizedSelected(int[] arr, int l, int r, int k) {
        if (l >= r) {
            return;
        }
        int pos = randomizedPartition(arr, l, r);
        int num = pos - l + 1;
        if (k == num) {
            return;
        } else if (k < num) {
            randomizedSelected(arr, l, pos - 1, k);
        } else {
            randomizedSelected(arr, pos + 1, r, k - num);
        }
    }

    // 基于随机的划分
    private int randomizedPartition(int[] nums, int l, int r) {
        int i = new Random().nextInt(r - l + 1) + l;
        swap(nums, r, i);
        return partition(nums, l, r);
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, r);
        return i + 1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/972727.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号