<>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,
Solve in servlet The Chinese output in is a question mark C String function and character function in language MySQL management 35 A small coup optimization Java performance —— Concise article Seven sorting algorithms (java code ) use Ansible Batch deployment SSH Password free login to remote host according to excel generate create Build table SQL sentence Spring Source code series ( sixteen )Spring merge BeanDefinition Principle of Virtual machine installation Linux course What are the common exception classes ?