<>TopK problem

Input array arr, Find the biggest one k number . for example , input 4,5,1,6,2,7,3,8 this 8 A number , Then the biggest 4 The first number is 5,6,7,8.
Example 1 ：
input ：arr = [3,2,1], k = 2
output ：[3,2] perhaps [2,3]
Example 2 ：
input ：arr = [0,1,2,1], k = 1
output ：

<> Realm one

The code is as follows ：
// Commutative function void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }
// Downward adjustment of the stack （ Small pile ） void AdjustDown(int* a, int n, int parent) {
//child Record the subscript of the child with the smaller median value between the left and right children int child = 2 * parent + 1;// First, the default value of the left child is smaller while (child <
n) { if (child + 1 < n&&a[child + 1] < a[child])// The right child exists and the right child is younger than the left child { child++;
// The younger child changed to the right child } if (a[child] < a[parent])// The value of the smaller of the left and right children is smaller than that of the parent node { // Exchange the parent node with the smaller child node
Swap(&a[child], &a[parent]); // Continue to adjust downward parent = child; child = 2 * parent + 1;
} else// It's piled up { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k,
int* returnSize) { *returnSize = k; int i = 0; // Jianxiaodui for (i = (arrSize - 1 - 1)
/ 2; i >= 0; i--) { AdjustDown(arr, arrSize, i); } // In descending order int end = arrSize - 1;
while (end > 0) { Swap(&arr, &arr[end]); AdjustDown(arr, end, 0); end--; }
// Will be the biggest k The number is stored in the array int* retArr = (int*)malloc(sizeof(int)*k); for (i = 0; i < k; i++)
{ retArr[i] = arr[i]; } return retArr;// Return the largest k number }
Time complexity ： O ( N + N l o g N ) O(N+NlogN) O(N+NlogN)  Spatial complexity ： O ( N ) O(N) O(N)

<> Realm two

The time complexity of a downward adjustment is O ( l o g N ) O(logN) O(logN), However, the time complexity of one reactor build is 0 O ( N ) O(N)
O(N).

The code is as follows ：
// Commutative function void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }
// Downward adjustment of the stack （ Heaps ） void AdjustDown(int* a, int n, int parent) {
//child Record the subscript of the child with the larger median value between the left and right children int child = 2 * parent + 1;// First, the default value of the left child is larger while (child <
n) { if (child + 1 < n&&a[child + 1] > a[child])// The right child exists and the right child is older than the left child { child++;
// The older child changed to the right child } if (a[child] > a[parent])// The value of the older of the left and right children is larger than that of the parent node { // Exchange the parent node with the larger child node
Swap(&a[child], &a[parent]); // Continue to adjust downward parent = child; child = 2 * parent + 1;
} else// It's piled up { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k,
int* returnSize) { *returnSize = k; int i = 0; // Build a pile for (i = (arrSize - 1 - 1)
/ 2; i >= 0; i--) { AdjustDown(arr, arrSize, i); } // Will be the biggest k The number is stored in the array int* retArr = (
int*)malloc(sizeof(int)*k); int end = arrSize - 1; for (i = 0; i < k; i++) {
retArr[i] = arr;// Take the top data Swap(&arr, &arr[end]);// Exchange top data with last data
// Make a downward adjustment , Do not regard the last data as the data to be adjusted , So the data to be adjusted is end=arrSize-1 AdjustDown(arr, end, 0); end--
;// Subscript change of the last data } return retArr;// Return the largest k number }
Time complexity ： O ( N + k l o g N ) O(N+klogN) O(N+klogN)  Spatial complexity ： O ( N ) O(N) O(N)

<> Realm three

storage 100 How much memory space does 100 million integers need ? Let's make a rough estimate ：
We know that 1KB=1024byte,1MB=1024KB,1GB=1024MB, So it can be concluded that 1GB Probably 230 Bytes , in other words 1GB About equal to 10 100 million bytes .

storage 100 100 million integer needs 400 100 million bytes , So storage 100 100 million integer data needed 40G Left and right memory space . The space complexity of the former two algorithms are both low O(N), It is not suitable for this kind of massive data processing .

The code is as follows ：
// Commutative function void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; }
// Downward adjustment of the stack （ Small pile ） void AdjustDown(int* a, int n, int parent) {
//child Record the subscript of the child with the smaller median value between the left and right children int child = 2 * parent + 1;// First, the default value of the left child is smaller while (child <
n) { if (child + 1 < n&&a[child + 1] < a[child])// The right child exists and the right child is younger than the left child { child++;
// The younger child changed to the right child } if (a[child] < a[parent])// The value of the smaller of the left and right children is smaller than that of the parent node { // Exchange the parent node with the smaller child node
Swap(&a[child], &a[parent]); // Continue to adjust downward parent = child; child = 2 * parent + 1;
} else// It's piled up { break; } } } int* getLeastNumbers(int* arr, int arrSize, int k,
int* returnSize) { *returnSize = k; if (k == 0) return NULL; // Use the first part of the array K Build a small pile int i
= 0; int* retArr = (int*)malloc(sizeof(int)*k); for (i = 0; i < k; i++) { retArr
[i] = arr[i]; } for (i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(retArr, k, i
); } // The rest N-k The number is compared with the top data in turn for (i = k; i < arrSize; i++) { if (arr[i]>retArr) {
retArr = arr[i];// Top data replacement } AdjustDown(retArr, k, 0);// Make a downward adjustment } return
retArr;// Return the largest k number }
Time complexity ： O ( k + N l o g k ) O(k+Nlogk) O(k+Nlogk)  Spatial complexity ： O ( k ) O(k) O(k)

Technology
Daily Recommendation