Topic:

Design an algorithm to find the smallest k number in an array. You can return these k numbers in any order.

Example:

[1,2,3,4] class Solution {public int[] smallestK(int[] arr, int k) {}}Copy the code

Answer key:

Using the heap method to solve the problem:

We use a large root heap to maintain the pre-k values of the array in real time. The first k number is first inserted into the large root heap, and then iterated from the k+1 number. If the number currently iterated is smaller than the number at the top of the large root heap, the number at the top of the heap is popped up, and then the number currently iterated is inserted. Finally, store the number in the large root heap into an array and return it. We can do this since the heap (priority queue) in C++ is a large root heap. In Python, pairs are small root heaps, so we need to take the negative of all the numbers in the array to maintain the pre-k small value using the small root heap. The Java heap, even if it defaults to a small root heap, can be manually replaced with a large root heap.

class Solution { public int[] smallestK(int[] arr, int k) { int[] vec = new int[k]; If (k == 0) {return vec; } PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer num1,  Integer num2) { return num2 - num1; }}); for (int i = 0; i < k; ++i) { queue.offer(arr[i]); } for (int i = k; i < arr.length; ++i) { if (queue.peek() > arr[i]) { queue.poll(); Queue. Offer (arr[I]); // Insert the element and return false when the insert fails}} for (int I = 0; i < k; ++i) { vec[i] = queue.poll(); } return vec; }}Copy the code

Ideas:

If you take the big root heap, the first k is already the big root heap, you just take the largest, the KTH largest, and every time you compare it to the next, the first K is going to be the smallest k

The priorityQueue in Java will be covered in the next blog post!