<>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 :[2]

<> 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[0], &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[0];// Take the top data Swap(&arr[0], &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[0]) {
retArr[0] = 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
©2019-2020 Toolsou All rights reserved,
Huawei 2021 session Hardware Engineer Logical post (FPGA) Super detailed surface !!!Vue-element-admin upgrade ui edition virtual machine VMware Download and install the most detailed tutorial !C++ Move constructor and copy constructor sound of dripping water java Backstage interview pygame Realize full screen mode and adjustable window size mysql Database setting character set configuration modification my.ini file (windows)30 What's the experience of being a junior programmer at the age of 20 C++ Multithreading programming ( Summary of common functions and parameters )python_ cherry tree