题目 :输入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)
题目: 思路: 思路一:直接利用快速排序的方法对数组进行排序,时间复杂度为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踢出,将新值放入,重新构建堆。重复以上步骤直至循环结束。
题目描述 输入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
K个数。...例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。...这一题的思路和上题类似,仅仅是换成了k个前。 这种算法是受快速排序算法的启发。...这样遍历一边数组后,得到一个k个数字的最大堆,这个最大堆里存的是最小的k个数。...()); 有的小伙伴会问,为啥最大堆是最小的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简洁、高效。
题目描述 描述 给定一个长度为 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 的最小堆过程如下...应该使用大顶堆来维护最小堆,而不能直接创建一个小顶堆并设置一个大小,企图让小顶堆中的元素都是最小元素。
一、题目描述 输入整数数组 arr ,找出其中最小的 k 个数。例如,输入 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4 。...= arr.length <= 10000 0 <= arr[i] <= 10000 二、题目解析 这道题目最简单粗暴的方法当然是将数组 arr 按照从小到大的顺序整体排序之后,获取数组的前 k 个数就行...而整体排序的算法有很多种选择,比如冒泡、选择、快速、堆排序等等。 这种暴力解法肯定不是面试官想要的回答,因为我们没有利用好题目的全部条件。 再读一下这句话:找出其中最小的 k 个数。...* 2)、index 等于 k,说明从 0 到 index 这个区间中的所有元素就是那些最小的 k 个数,将其返回。...* 3)、index 大于 k,说明从 0 到 index 这个左侧区间中的元素超过了 k 个,那么最小的 k个数肯定是都在在这个区间,而中间、右侧区间均可以不去处理,只需要继续对左侧区间进行快速排序即可
如果你是个算法菜鸡(和我一样),那么最推荐的是先把剑指offer的题目搞明白。...例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。...这一题的思路和上题类似,仅仅是换成了k个最小的数字。 这种算法是受快速排序算法的启发。...这样遍历一边数组后,得到一个k个数字的最大堆,这个最大堆里存的是最小的k个数。...()); 有的小伙伴会问,为啥最大堆是最小的k个数?
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小的元素
和高速排序有点类似,利用高速排序的划分算法, 划分算法见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++
1,问题简述 设计一个算法,找出数组中最小的k个数。 以任意顺序返回这k个数均可。...2,示例 输入:arr = [1,3,5,7,2,4,6,8], k = 4 输出:[1,2,3,4] 3,题解思路 有两种解法,第一种是数据装入集合,对集合进行升序排序,查找前k个元素;第二种是对数组进行排序...,将k的元素装入新数组中。...} Arrays.sort(arr); int[] result = new int[k]; if (k >= 0) { System.arraycopy...[] arr, int k) { if (arr == null || arr.length == 0 || arr.length < k) { return new
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...(arr); int[] array = new int[k]; if (k >= 0) { System.arraycopy(arr, 0, array..., 0, k); } return array; } public static int[] smallestK2(int[] arr, int k)...最近一段时间的输出文章都是自己之前做过的内容,自己打算将做过的题都整理成一篇篇文章进行梳理一下,喜欢看java的文章可以查看历史记录,本人写过Mybatis框架的系列文章,包括简单的增删改查,高级用法,
关键词: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个数就是我们想要的。
最小的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)
概要 题目描述 输入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
1,问题简述 输入整数数组 arr ,找出其中最小的 k 个数。 例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。...2,示例 示例 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 3,题解思路 使用排序,队列的方式进行解决 4,题解程序 import java.util.Arrays...] result = new int[k]; if (k >= 0) { System.arraycopy(arr, 0, result, 0, k);...总结一下 这道题给出了两个题解思路,两种方式都是比较容易理解的,这里就没有给出过多的注释说明,队列的特点在之前的文章中多次说明了,就是先进先出,但是对于应用的开发者来说,熟悉队列的特点也是有必要的,这里就简单的说下
每期1-2个算法,也有可能是一个类别。 文章包括题目、思路以及代码。 如果您对本期有不同或者更好的见解,请后台留言,喜欢请点个好看,谢谢阅读。 题目 输入n个整数,找出其中最小的K个数。...例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。...思路 1.把前k个数构建一个大顶堆 2.从第k个数开始,和大顶堆的最大值进行比较,若比最大值小,交换两个数的位置,重新构建大顶堆 3.一次遍历之后大顶堆里的数就是整个数据里最小的k个数。...代码 function GetLeastNumbers_Solution(input, k) { if (k > input.length) { return [];...} createHeap(input, k); for (let i = k; i < input.length; i++) { // 当前值比最小的k个值中的最大值小
题目描述 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。...class Solution { static public ArrayList GetLeastNumbers_Solution(int [] input, int k)...{ ArrayList list = new ArrayList(); if(input==null || k>input.length |...| k==0) return list; //存放k个值,按从大到小排列 PriorityQueue queue = new...//前k个直接存 if(i<k){ //PriorityQueue会自动排序 queue.offer(input[
最小的 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/
让我们举几个栗子: 给定整数1593212,删去3个数字,新整数的最小情况是1212 ? 给定整数30200,删去1个数字,新整数的最小情况是200 ?...给定整数10,删去2个数字,新整数的最小情况是0 ? 需要注意的是,给定的整数大小可以超过long类型的范围,所以需要用字符串来表示。 ? ? ? ? ? ? ? ? ———————————— ?...很简单,我们把原整数的所有数字从左到右进行比较,如果发现某一位的数字大于它右面的数字,那么在删除该数字后,必然会使得该数位的值降低,因为右面比它小的数字顶替了它的位置。.../** * 删除整数的k个数字,获得删除后的最小值 * @param num 原整数 * @param k 删除数量 */ public static String removeKDigits.../** * 删除整数的k个数字,获得删除后的最小值 * @param num 原整数 * @param k 删除数量 */ public static String removeKDigits
领取专属 10元无门槛券
手把手带您无忧上云