Enter n integers and find the smallest K number. For example, if you enter the eight digits 4,5,1,6,2,7,3,8, the smallest four digits are 1,2,3,4. It is very simple to analyze the problem, and output the first K directly after ascending sort, but the time complexity should be considered. Heap sort can be used to build a large top heap with k values, and then compare the heap head with other values. The large heap head values are swapped and adjusted until the k values are the smallest. The time complexity is nlogk. Code to import the Java. Util. ArrayList; public class HeapKthMin { public static void main(String[] args) { // TODO Auto-generated method stub int[] nums = 6,7,5,1,9,8,2,3,4 {}; ArrayList
list = getLeastNumber(nums, 5); for(int num: list){ System.out.println(num); } } public static ArrayList
getLeastNumber(int[] input, int k){ ArrayList
res = new ArrayList<>(); if(input==null || input.length==0 || input.length
=0; i–){ adjustHeap(input, i, k-1); } for(int i=k; i
nums[child]){ break; } nums[position] = nums[child]; position = child; } nums[position] = temp; }} — — — — — — — — — — — — — — — — — — — — — the author: another source I actually exist: the original CSDN: blog.csdn.net/qq_24034545… Copyright notice: This article is the blogger’s original article, reprint please attach the blog link!
For more learning materials: Annalin1203