Offer 40. Minimum number of k
Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.
1. Title 📑
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 = 2
Output: [1,2] or [2,1]
Example 2:
Input: arr = [0,1,2,1], k = 1
Output: [0]
Limitations:
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
2. Ideas 🧠
Method 1: fast sort through the first K
Use the time complexity of quick sort O(NlogN) to sort, take the first k elements in the array, you can get the result.
Method two: heap
PriorityQueue is a small root heap by default, so you need to redefine the compare method to a large root heap.
Large root heap declaration:
PriorityQueue<Integer> pq = new PriorityQueue<>(arr.length, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return (o2 - o1) > 0 ? 1 : -1; }});Copy the code-
Sentence: arr = = null | | k = = 0 directly returns an empty array.
-
Put the first K numbers into the heap one by one
- When the number of digits in the heap is greater than K, determine the size of the number of the top element and the number of the next element to enter the heap
- If the number of the top element is larger than the number of the next element to enter the heap, its element is ejected and the new element is added to the heap, keeping the first K elements as the smallest element scanned so far.
-
Until the last element position is scanned, pop the first k elements in the heap one by one to get the answer.
Method 3: Optimize quicksort
First, you need to understand and understand the basic idea of quicksort in order to flexibly transform it.
The code is the same as the quicktype code, but with a few more lines of judgment, so it’s very important to the underlying idea
if (i > k) quick_sort(q, l, j, k)I corresponds to the left subscript of each binary, ifi比kBig words, indicating at this timei在kTo the left of, we just need to put the front of the arrayjSort it, and you’re doneelse quick_sort(q,j + 1, r, k)ifk比iBig words, indicating at this timei在kTo the right of, it indicates that there is not enough need at this time, we need to continue to divide the right until we find what we need againifOperation.
Less nonsense ~~~~~ on the code!
3. Code: 👨💻
Commit AC for the first time
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
quickSort(arr, 0, arr.length - 1);
int res [] = new int[k];
for(int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
public static void quickSort(int arr[], int l, int r) {
if (l >= r) return ;
int i = l - 1;
int j = r + 1;
int mid = arr[(l + r) >> 1];
while(i < j) {
do i++; while(arr[i] < mid);
do j--; while(arr[j] > mid);
if(i < j) swap(arr, i, j);
}
quickSort(arr, l, j);
quickSort(arr, j + 1, r);
}
public static void swap(int arr[], int i, int j) {
inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the codeTime complexity: O(NlogN) N is the length of array ARr
Spatial complexity: The average recursive depth of O(N) quicksort is O(logN), and the worst case is O(N).
Commit the SECOND TIME
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(arr == null || k == 0) {
return new int [0];
}
PriorityQueue<Integer> pq = new PriorityQueue<>(arr.length, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return (o2 - o1) > 0 ? 1 : -1; }});for(int num : arr) {
if(pq.size() < k) {
pq.offer(num);
}else if(pq.peek() > num) { pq.poll(); pq.offer(num); }}int res[] = new int [k];
for(int i = 0; i < k; i++) {
res[i] = pq.poll();
}
returnres; }}Copy the codeTime complexity: O(N) N is the heap size K
Space complexity: O(N log N) The time complexity of both heap-in and heap-out operations is O(logk). Each element needs to perform a heap-in operation.
Commit AC for the third time
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
quick_sort(arr, 0, arr.length - 1, k);
int res [] = new int[k];
for(int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
public static void quick_sort(int q[], int l, int r, int k) {
if (l >= r) return ;
int i = l - 1;
int j = r + 1;
int mid = q[(l + r) >> 1];
while(i < j){
do i++; while (q[i] < mid);
do j--; while (q[j] > mid);
if(i < j) swap(q, i, j);
}
if (i > k) quick_sort(q, l, j, k);
else quick_sort(q,j + 1, r, k);
}
public static void swap(int arr[], int i, int j){
inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }}Copy the codeTime complexity: O(N) N is the length of array ARr, and there are N + N/2 + N/4 +…… = 2n-1, that is, the time complexity is O(N).
Space complexity: O(logN) The average recursion depth of partition function is O(logN).
4, summarize
The topic array, the underlying data structure to understand, and then familiar with the underlying ideas of fast row, how to carry out each operation. Familiar with the structure of the heap, in JDK8 if the use of large root heap, small root heap to master.
Quick row template:
public static void quick_sort(int q[], int l, int r, int k) {
if (l >= r) return ;
int i = l - 1;
int j = r + 1;
int mid = q[(l + r) >> 1];
while(i < j){
do i++; while (q[i] < mid);
do j--; while (q[j] > mid);
if(i < j) swap(q, i, j);
}
quick_sort(q, l, j, k);
quick_sort(q,j + 1, r, k);
}
public static void swap(int arr[], int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Copy the code❤️ from the LeetCode Basic Algorithms column subscribe to ❤️
The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.
If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!
Offer 40. Minimum number of k