最小的k个数算法_最小k个数最简单算法_最大k个数最快算法 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

最小的K个数

题目：思路：思路一：直接利用快速排序的方法对数组进行排序，时间复杂度为O(NlogN)，简单便捷，排完序之后便是有序的数组，直接去前K个数出来思路二：根据一次快排(Partition)的想法，我们知道一次随机快速排序可以确定一个有序的位置...，这个位置的左边都小于这个数，右边都大于这个数，我们如果能找到随机快速排序确定的位置等于k-1的那个位置，那么0-k-1个数就是我们要找的数。...如果Partition确定的位置大于K-1，说明k-1这个位置在它的左边，我们继续在左边进行查找。缺点：这种方法的时间复杂度虽然是O(n)，但是找出来的最小的K个数却不是排序过的。...而且这种方法有个限制，就是必须修改给的数组。思路三：利用大顶堆或小顶堆的思路，就是循环一遍数组，先直接将数组的前K个数直接塞入数组TEMP，构建堆。...然后从第K个数开始循环，先取出TEMP的第k-1个数值（即最大或者最小），进行比较，如果符合条件（即大于或小于），将堆的K-1踢出，将新值放入，重新构建堆。重复以上步骤直至循环结束。

2931 0

最小的K个数

题目 :输入n个整数，找出其中最小的K个数。...例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4 思路: 遍历数组先取数组的前k个数建立大根堆,继续遍历数组.如果当前值比大根堆最大值小,那么将数组中这个小值替换到堆里...代码: //输入n个整数，找出其中最小的K个数。 // 例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。...public static ArrayList GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer...}); //2,41,5,2,5,3,4,23 for(int i=0;i<input.length;i++){ if (i<k)

2942 0

您找到你想要的搜索结果了吗？

是的

没有找到

最小的 k 个数！

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。一、题目描述输入整数数组 arr ，找出其中最小的 k 个数。...而整体排序的算法有很多种选择，比如冒泡、选择、快速、堆排序等等。这种暴力解法肯定不是面试官想要的回答，因为我们没有利用好题目的全部条件。再读一下这句话：找出其中最小的 k 个数。...所在的下标 index 与 k 的关系 * 1)、index 小于 k，说明从 0 到 index 这个左侧区间中的元素不足 k 个，那么最小的 k 个数肯定部分是在这个区间，还需要继续在右侧区间中去寻找出一部分元素来填充...，因此对对右侧区间进行快速排序即可 * 2)、index 等于 k，说明从 0 到 index 这个区间中的所有元素就是那些最小的 k 个数，将其返回。...* 3)、index 大于 k，说明从 0 到 index 这个左侧区间中的元素超过了 k 个，那么最小的 k个数肯定是都在在这个区间，而中间、右侧区间均可以不去处理，只需要继续对左侧区间进行快速排序即可

3682 0

最小的 K 个数

题目描述描述给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。...例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。...数据范围：0≤k,n≤10000，数组中每个数的大小0 ≤val≤1000 要求：空间复杂度 O(n) ，时间复杂度 O(nlogn) 输入： [4,5,1,6,2,7,3,8],4 返回值： [1,2,3,4...] 说明：返回最小的4个数即可，返回[1,3,2,4]也可以解题思路大小为 K 的最小堆时间复杂度：O(NlogK) 空间复杂度：O(K) 特别适合处理海量数据维护一个大小为 K 的最小堆过程如下...应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。

3612 0

最小的k个数

，或者有空间限制等，尽量体现在代码中，保证读者可以不漏掉书中细节）尽量精简话语，避免冗长解释给出代码可运行，注释齐全，对细节进行解释题目介绍输入n个整数，找出其中最小的K个数。...例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。...方法一：基于快速排序的变种 O（n）思路该方法需要改变原数组。还记得上一题：数组中超过一半的数字么？这一题的思路和上题类似，仅仅是换成了k个最小的数字。这种算法是受快速排序算法的启发。...这样遍历一边数组后，得到一个k个数字的最大堆，这个最大堆里存的是最小的k个数。...()); 有的小伙伴会问，为啥最大堆是最小的k个数？

9362 0

最小的k个数

题目输入整数数组 arr ，找出其中最小的 k 个数。...例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4 示例：输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1] 条件： 1、0 <=...k <= arr.length <= 10000 2、0 <= arr[i] <= 10000 解答 //利用java自带函数 class Solution { public int[] getLeastNumbers...(int[] arr, int k) { //整体排序、去最小的k个数字 Arrays.sort(arr); return Arrays.copyOfRange(...arr,0,k); } } 分析利用java.util 支持的排序算法，使用API简洁、高效。

4252 0

最小的k个数

）：底部导航栏——剑指offer题解 CSDN（@Rude3Knife）：剑指offer题解专栏题目介绍输入n个整数，找出其中最小的K个数。...例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。...这样遍历一边数组后，得到一个k个数字的最大堆，这个最大堆里存的是最小的k个数。...()); 有的小伙伴会问，为啥最大堆是最小的k个数？...k个最小。

3713 0

最小的K个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。...解题思路两种方法：法1：先对数组排序，然后取出前k个法2：利用最大堆保存这k个数，每次只和堆顶比，如果比堆顶小，删除堆顶，新数入堆。...{ ArrayList res = new ArrayList(); if(input == null || k ==0 || k...{ ArrayList res = new ArrayList(); if(input == null || k ==0 || k...= k) maxHeap.offer(input[i]); else{ if(maxHeap.peek() > input

7682 0

java算法之寻找最小的k个数--1

1.快排,不讲了 2.定义一个小根堆,比如priorityqueue,添加数据,利用小根堆每次弹出最小值即可这个题目的两种解法都比较简单,时间复杂度也还好,就不讲这题了这里引入一个类似题目的变种...谷歌面试题：输入是两个整数数组，他们任意两个数的和又可以组成一个数组，求这个和中前k个数怎么做？...分析： “假设两个整数数组为A和B，各有N个元素，任意两个数的和组成的数组C有N^2个元素。...A[2]+B[3] <=… … A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <=… 问题转变成，在这N^2个有序数列里，找到前k小的元素

2362 0

求最小的k个数

和高速排序有点类似，利用高速排序的划分算法，划分算法见http://blog.csdn.net/buyingfei8888/article/details/8997803 依据int partition...(int number[],int start,int end)；返回值为数组下标，大小为index，index左边值均小于number【index】，右边均大于number【index】，若为k-1....start]=temp; } return end; } void getLeastNumber(int * input,int start,int end,int * output,int k)...= k-1){ if(index > k-1){ end = index -1; index = partition(input,start,end); } if(index...< k-1){ start = index + 1; index = partition(input , start , end ); } } for(int i=0;i<k;i++

2591 0

算法（六）二叉堆获取最小的k个数

关键词：heap 如果你有一个文件，里面包含20万行的整数，如何获取前k个最小的数？首先可以想到两个思路：将所有的数按从小到大排序，取前k个。...先读入前k个数到一个数组中（大小为k）并按从小到大排序，然后每读入一个新的数就将其放入数组中合适的排序位置。当所有的数都按这个规则被处理后，最终留在数组中的k个数就是我们想要的。...（具体代码见下文）假设我们的文件 20w_int.txt 包含20万行整数，三种方法取前k个最小数用时如下：（其中sort代表第一种思路，k-array代表第二种思路，heap代表堆这种思路） ?...直接用GNU sort就行，假设取前10个最小数： sort -n 20w_int.txt | head -10 第二种思路——k-array 先读入前k个数到一个数组中（大小为k）并按从小到大排序，...当所有的数都按这个规则被处理后，最终留在数组中的k个数就是我们想要的。

4913 0

牛客网-最小的k个数

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。...| k==0) return list; //存放k个值，按从大到小排列 PriorityQueue queue = new...//前k个直接存 if(i<k){ //PriorityQueue会自动排序 queue.offer(input[...i]); //存入list list.add(input[i]); //前k个之后的进行比较（与最大堆了堆顶元素比较...） }else{ //如果第i个元素 < 最大堆的顶元素就把最大堆的顶元素取出，然后重新把这个小的值存入 if(

3123 0

《剑指offer》最小的k个数

本系列是《剑指offer》或leetcode的JavaScript版本。每期1-2个算法，也有可能是一个类别。文章包括题目、思路以及代码。...如果您对本期有不同或者更好的见解，请后台留言，喜欢请点个好看，谢谢阅读。题目输入n个整数，找出其中最小的K个数。...例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。...思路 1.把前k个数构建一个大顶堆 2.从第k个数开始，和大顶堆的最大值进行比较，若比最大值小，交换两个数的位置，重新构建大顶堆 3.一次遍历之后大顶堆里的数就是整个数据里最小的k个数。...} createHeap(input, k); for (let i = k; i < input.length; i++) { // 当前值比最小的k个值中的最大值小

4291 0

LeetCode117|最小的k个数

1，问题简述输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。...0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000 3，题解思路使用排序，队列的方式进行解决 4，题解程序 import java.util.Arrays...] result = new int[k]; if (k >= 0) { System.arraycopy(arr, 0, result, 0, k);...} return result; } } 5，题解程序图片版 6，总结一下这道题给出了两个题解思路，两种方式都是比较容易理解的，这里就没有给出过多的注释说明，队列的特点在之前的文章中多次说明了...，就是先进先出，但是对于应用的开发者来说，熟悉队列的特点也是有必要的，这里就简单的说下

2631 0

LeetCode 40.最小的k个数

最小的 k 个数[1] 描述输入整数数组 arr ，找出其中最小的 k 个数。...例如，输入 4、5、1、6、2、7、3、8 这 8 个数字，则最小的 4 个数字是 1、2、3、4 解题思路现将传入的数组arr进行排序（任意排序方法皆可，此处采用冒泡）；新定义一个最终结果的int...型数组resultArr，长度为传入的k；将排序好的数组的前k个值传入上一步中所定义的数组resultArr中；返回最终结果数组resultArr；实现 /** * Created with IntelliJ...最小的k个数 */ import java.util.ArrayList; import java.util.Arrays; public class Forty { public static...最小的k个数: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/

3802 0

剑指offer——最小的K个数

概要题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。...---- 思路数组为空或k=0或者k大于数组长度则返回空。否则把数组元素一次输入到最小堆，然后一次删除前k个数并存入结果数组即可。...; class Solution { public: vector GetLeastNumbers_Solution(vector input, int k)...== 0 || input.size() == 0 || k > input.size()){ return ans; }...input.size() ; i++){ q.push(input[i]); } for(int i = 0 ; i < k

2894 0

Sword To Offer 029 - 最小的K个数

最小的K个数 Desicription 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。...Solution class Solution { public: vector GetLeastNumbers_Solution(vector input, int k)...{ if(input.size() < k) { return vector(0); } auto compare =...number : input) { priorityQueue.push(number); while(priorityQueue.size() > k)

2512 0

漫画学算法：删去k个数字后的最小值

让我们举几个栗子：给定整数1593212，删去3个数字，新整数的最小情况是1212 ? 给定整数30200，删去1个数字，新整数的最小情况是200 ?...给定整数10，删去2个数字，新整数的最小情况是0 ? 需要注意的是，给定的整数大小可以超过long类型的范围，所以需要用字符串来表示。 ? ? ? ? ? ? ? ? ———————————— ?...我们来举一个栗子：给定整数 541270936，要求删去一个数，让剩下的整数尽可能小。此时，无论删除哪一个数字，最后的结果都是从9位整数变成8位整数。.../** * 删除整数的k个数字，获得删除后的最小值 * @param num 原整数 * @param k 删除数量 */ public static String removeKDigits.../** * 删除整数的k个数字，获得删除后的最小值 * @param num 原整数 * @param k 删除数量 */ public static String removeKDigits

9193 0

LeetCode70|最小K个数

1，问题简述设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。...2，示例示例：输入：arr = [1,3,5,7,2,4,6,8], k = 4 输出：[1,2,3,4] 提示： 0 <= len(arr) <= 100000 0 <= k <= min(100000...; } } 5，题解程序图片版 6，总结排序在整个工作中还是比较的常用的一种场景，排序的目的是为了更加高效的检索自己需要的数据，对于数据库优化，为什么要加索引，难道不是为了更加高效的检索自己需要的数据嘛...最近一段时间的输出文章都是自己之前做过的内容，自己打算将做过的题都整理成一篇篇文章进行梳理一下，喜欢看java的文章可以查看历史记录，本人写过Mybatis框架的系列文章，包括简单的增删改查，高级用法，...都是工作中常用的，JDK源码也写了十几篇，MySQL文系列文章等都可以在历史文章进行查找的。

3811 0

LeetCode13|最小k个数

1，问题简述设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。...2，示例输入：arr = [1,3,5,7,2,4,6,8], k = 4 输出：[1,2,3,4] 3，题解思路有两种解法，第一种是数据装入集合，对集合进行升序排序，查找前k个元素；第二种是对数组进行排序...，将k的元素装入新数组中。...[] arr, int k) { if (arr == null || arr.length == 0 || arr.length < k) { return new...5，总结，这道题自己本来是用了第二种方式，当再次再看这道题进行总结时却用了第一种方式，真是让人琢磨不透的心，第一种方式的时间消耗却很多，觉得还是第二种方式还是比较好的

3332 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭