Today share a relatively simple topic, I hope you can master in 5 minutes!
01. Examples of topics
The smallest number of k |
---|
Enter the integer array arr to find the smallest k number. For example, if you enter 4, 5, 1, 6, 2, 7, 3, and 8, the smallest four digits are 1, 2, 3, and 4. |
Example 1:
Input: arr = [3,2,1], k = 2Output: [1,2] or [2,1]Copy the code
Example 2:
Input: arr = [0,1,2,1], k = 1Output: [0]Copy the code
Limitations:
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
Copy the code
02, Heap and size top heap
This question comes from “Finger offer”, which is a very frequent question. It can be solved by sorting and so on. But here, we use the more classical ** big top heap (big root heap) ** solution to solve. Because I know a lot of people are probably confused, so let’s go over the big top heap.
A Heap is a general term for a special kind of data structure in computer science. We usually refer to an array object that can be viewed as a complete binary tree. If you don’t remember what a complete binary tree is, you can review this article:
Binomial Trees Lecture 7 – Complete Binomial Trees (222)
The property of the heap is that the value of the parent node is always greater or smaller than the value of its two children. If the parent node is larger than both of its children, we call it the big top heap. If the parent node is smaller than both of its children, we call it the small top heap.
We number the nodes in the heap by layer, and we map this logical structure to an array like this.
The big top heap satisfies the following formula:
arr[i] >= arr[2i 1] && arr[i] >= arr[2i 2]
The same goes for the small top heap:
The small top heap satisfies the following formula:
arr[i] <= arr[2i 1] && arr[i] <= arr[2i 2]
03. Topic analysis
We learned about the big top heap, now let’s think about how to solve it with the big root heap.
First, we create a large top heap of size K. If the array is [4,5,1,6,2,7,3,8], k=4. Something like this:
I’m sure there are some people here who don’t know how to build stacks. Remember: For an unmaintained heap (a complete binary tree), we can start tweaking from the parent of its last node. This does not need to memorize, in fact, is a layer of adjustment process.
Adjusts from the parent of the last node
Keep going up
Keep going up
The code for heap adjustment looks something like this:
/ / build the heap. For a heap that has not yet been maintained, adjust from the parent of its last node.
private void buildHeap(int[] nums) {
// The last node
int lastNode = nums.length - 1;
// Remember: parent = (i-1) / 2 left = 2 * I 1 right = 2 * I 2;
// The parent of the last node is 7 int startHeapify = (lastNode - 1) / 2; while (startHeapify >= 0) { // Adjust the heap building process heapify(nums, startHeapify--); } } // The process of adjusting the big top heap private void heapify(int[] nums, int i) { // If there is a larger number of nodes than the left and right nodes of the current node, then switch and continue the maintenance of the switched node int len = nums.length; if (i >= len) return; // Left and right child nodes int c1 = ((i << 1) 1), c2 = ((i << 1) 2); // Assume that the current node is the largest int max = i; // If the left child node is large, update Max = c1; if (c1 < len && nums[c1] > nums[max]) max = c1; // If the right child node is large, update Max = c2; if (c2 < len && nums[c2] > nums[max]) max = c2; // If the largest number is not node I, heapify(nums, Max) adjusts the subtree of node I. if(max ! = i) { swap(nums, max, i); // recursive processing heapify(nums, max); } } private void swap(int[] nums, int i, int j) { nums[i] = nums[i] nums[j] - (nums[j] = nums[i]); } Copy the code
Then we iterate through the rest of the array starting with k. If the element is smaller than the heaptop element, the heaptop element is fetched and the current element is added to the heap. In the example above, 2 is put into the heap because it is less than the top of the heap element 6. We found that the current complete binary tree does not satisfy the big top heap, so we adjusted it.
Before the adjustment
After the adjustment
Repeat the above steps, adding 7,3, and 8 to the heap. Here, since 7 and 8 are bigger than 5 at the top of the heap, only 3 will go in.
Before the adjustment
After the adjustment
The heap that we end up with is what we want. Since the size of the heap is K, the space complexity is O(K) and the time complexity is O(NlogK).
According to the analysis, complete the code:
//java
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0)
return new int[0];
int len = arr.length; if (k == len) return arr; // Create a heap for the first k of the arR array int[] heap = new int[k]; System.arraycopy(arr, 0, heap, 0, k); buildHeap(heap); // Build a heap for the smaller trees behind for (int i = k; i < len; i++) { if (arr[i] < heap[0]) { heap[0] = arr[i]; heapify(heap, 0); } } // Return the heap return heap; } private void buildHeap(int[] nums) { int lastNode = nums.length - 1; int startHeapify = (lastNode - 1) / 2; while (startHeapify >= 0) { heapify(nums, startHeapify--); } } private void heapify(int[] nums, int i) { int len = nums.length; if (i >= len) return; int c1 = ((i << 1) 1), c2 = ((i << 1) 2); int max = i; if (c1 < len && nums[c1] > nums[max]) max = c1; if (c2 < len && nums[c2] > nums[max]) max = c2; if(max ! = i) { swap(nums, max, i); heapify(nums, max); } } private void swap(int[] nums, int i, int j) { nums[i] = nums[i] nums[j] - (nums[j] = nums[i]); } } Copy the code
Execution Result:
I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download