Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how to solve the problem of Top-K by Java". In daily operation, I believe many people have doubts about how to solve the problem of Top-K by Java. The editor has consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubt of "how to solve the problem of Top-K by Java". Next, please follow the editor to study!

Title

Find the minimum number of K

Design an algorithm to find out the minimum number of k in the array. You can return this k number in any order.

Method one of the solution to the problem

Sort (Bubble / Select)

Train of thought

1. Bubble sorting is performed each time, the final position is determined, and after K times, the result can be obtained. The time complexity is O (n * k), when k maxNum) {maxIndex = j; maxNum = arr [j] }} if (maxIndex! = I) {swap (arr, maxIndex, I);} ret [I] = arr [I];} return ret;} public static void swap (int [] arr, int a, int b) {int temp = arr [a]; arr [a] = arr [b] Arr [b] = temp;} method II

Divide and conquer-quick sort

Train of thought

1. The core of quick sorting is the idea of divide-and-conquer. First, the sequence is divided into two parts by divide-and-conquer partition, and then the two parts are recursed again.

2, using the divide-and-conquer idea, that is, divide the operation partition, adjust the sequence according to the main element pivot, put the larger than pivot on the left end and the smaller than pivot on the right end, so as to determine the position pivotIndex of the main element pivot. If the pivotIndex happens to be KMuk 1, then the number of the pre-top 1 position is the first k large element, that is, the top K we require.

Time complexity: O (n)

Code implementation

Public static int [] topKByPartition (int [] arr, int k) {if (arr.length = = 0 | | kkmur1) {return quickSort (arr,low,pivotIndex-1,k);} else {return quickSort (arr,pivotIndex+1,high,k);}} public static int partition (int [] arr, int low, int high) {if (high-low = = 0) {return low;} int pivot = arr [high]; int left = low Int right = high-1; while (left

Pivot) {left++;} while (left < right & & arr [right] < pivot) {right--;} if (left < right) {swap (arr,left,right);} else {break;}} swap (arr,high,left); return left } public static void swap (int [] arr,int a, int b) {int temp = arr [a]; arr [a] = arr [b]; arr [b] = temp;} method 3

Utilization reactor

Train of thought

1, build a maximum heap

2. Traverse the original array, and the element is queued. When the heap size is K, you only need to compare the heap top element with the next element. If it is larger than the heap top element, delete the heap top element and insert it into the heap until all the elements have been traversed.

3. Dequeue the number of K stored in queue.

Time complexity: O (N*logK)

Code implementation

Public class TopK {public int [] smallestK (int [] arr, int k) {int [] ret = new int [k]; if (krypton0 | | arr.length==0) {return ret } / / 1, to build a maximum heap / / JDK priority queue is the minimum heap, we need to use our comparator Queue queue = new PriorityQueue (new Comparator () {@ Override public int compare (Integer o1, Integer o2) {return o2-o1;}})) / / 2, traverse the original array and join the queue for (int value:arr) {if (queue.size () < k) {queue.offer (value);} else {if (value < queue.peek ()) {queue.poll (); queue.offer (value) } / / 3, put the K elements stored in queue out of the for (int I = 0 [I] < kwiti +) {ret [I] = queue.poll ();} return ret;}} at this point, the study on "how to solve the Top-K problem by Java" is over, hoping to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.