NC119 最小的K个树

目录

最小的K个数

题目

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

示例 1:

输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]

示例 2:

输入:arr = [0,1,2,1], k = 1
输出:[0]

限制:

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解-优先队列

堆排序算法

Java实现了堆结构,为了熟悉知识点这里直接使用。

先把所有数据放进堆种,默认排序时升序。
输出前k个数就是最小的K个数。


class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int len = arr.length;
        int [] res  = new int[k] ;
        if (k == 0 || len == 0) {
            return res;
        }
       Queue<Integer> q = new PriorityQueue<>();
       for(int num :arr){
           q.offer(num); //全部放进去
       }
       for(int i=0;i<k;i++){
         res[i] = q.poll(); //输出前k个数
       }
       return res;
    }
}

这样数组有多大,优先队列就需要有多大。能不能较少优先队列的大小?

这里想到了另外一种思路,保持优先队列的大小就为K,里面存储最小的K个元素。
当队列中没有k个元素时直接入队,当队列中满了K个元素时,新元素与队列中最大的元素比较,所以这里队列应该采用降序排列,这样队头元素就是队列中的最大值。

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        //采用降序排列
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: arr) {
			//当队列中没有k个元素时直接入队
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {//当队列中满了K个元素时,新元素与队列中最大的元素比较。比最大的小,最大的出队,小的入队
                pq.poll();
                pq.offer(num);
            }
        }
        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}

题解-快速排序

推荐这些技术文章:

【每日一题】【优先队列、迭代器、lambda表达式】2022年1月15日-NC119 最小的K个数

描述

给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围:0\le k,n \le 100000≤k,n≤10000,数组中每个数的大小0 \le val \le 10000≤val≤1000
要求:空间复杂度 O(n)O(n) ,时...

数组的选择排序方法

public static void main(String[] args) {
//选择排序
int[] arr = {5, 4, 3, 2, 1,6};
//方式1
paiXu(arr);
//方式2
// selectSort(arr);
for (int i = 0; ...

最小的第k个数

我么是采用优先队列来做的,其实就是堆。

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
...

寻找最小的K个数

同上一篇,使用堆排序的方式做。
第一步构建最小堆,构建好之后数组的第一个元素就是最小的;
第二步排序,开始执行k-1次sift,每次将剩余元素中最小的元素放到未排序元素的末尾
 

func getLeastNumbers(arr []int, k int) []int {
if k == 0 {
return []int{}
}
buildMinHeap(arr)
for...

24.线性查找

public static int seqSearch(int[] arr, int value) {
// 线性查找是逐一比对,发现有相同值,就返回下标
for (int i = 0; i < arr.length; i++) {
if(arr[i] == value) {
return i;
}
}
return -1;...

【墨鳌】【798. 得分最高的最小轮调】

class Solution {
public:
int bestRotation(vector<int>& A) {
int N = A.size();
vector<int> mark(N, 0);
for (int i = 0; i < N; ++i) {
int L = ...

C语言:既能求最大公约数又能求最小公倍数的函数

int gygb(int a,int b,int m)
{
int t,c,gy,gb;
if(a>b) t=a,a=b,b=t;
for(c=a;c>=1;c--)
{
if(b%c==0 && a%c==0)

{
if(m==0) return c;
...

剑指 Offer 40. 最小的k个数

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

示例 1:
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:
输入:arr = [0,1,2,1], k = 1
输出:[0]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com...

378. 有序矩阵中第 K 小的元素&&373. 查找和最小的 K 对数字(多路并归 优先队列 || 二分查找)

链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
题目
给你一个 n x n 矩阵 matrix ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。
请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。

用例
示例 1:
输入:m...

题目001 使用PriorityQueue 获取最大/最小N个数

public class PriorityQueueTest {
private static PriorityQueue<Integer> maxHeap, minHeap;

public static void main(String[] args) {
int[] arr = {7, 5, 15, 3, 17, 2, 20, 24, 1, 9...

文章标题:NC119 最小的K个树
文章链接:https://www.dianjilingqu.com/4523.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>