For reprinting, please indicate the source: http://blog.csdn.net/ns_code/article/details/26966159

Title Description:

Enter n integers and find out the smallest number of K. For example, if you input 8 digits: 4, 5, 1, 6, 2, 7, 3, 8, the smallest 4 digits are 1, 2, 3, 4.

Input:

each test The case consists of two lines:

The first action is two integers n, K (1 <= n, K <= 200000), representing the length of the array.

The second line contains n integers, representing the n numbers. The range of the numbers in the array is [0,1000,000,000].

Output:

For each test case, output the smallest number of k, and print in order from small to large.

Sample input:

8 4

4 5 1 6 2 7 3 8

Sample output:

1 2 3 4

Thoughts:

1. The most intuitive way of thinking is still to sort arrays quickly and then take out the first k elements. Such time complexity is O(nlogn)

2. Similar can be used here Topic above Partition-based method, only this time the demarcation point is not the median, but the smallest k, that is, the elements that should be located in the k-1 position of the array after sorting, so that the k elements in front of the demarcation point (including the demarcation point) is the smallest K number (this K number is not necessarily sorted). The average time complexity of this method is O(n), and in the worst case it is O(n*n), just as in the analysis of the above topic, it can also be used. algorithm The method of dividing the array proposed in the introduction controls the time complexity in the worst case to O(n).

The code is as follows:

1. #include<stdio.h>  
2. #include<stdlib.h>  
3. #include<time.h>  
4.   
5. void Swap(int *a,int *b)  
6. {  
7.     if(*a != *b)  
8.     {  
9.         *a = *a + *b;  
10.         *b = *a - *b;  
11.         *a = *a - *b;  
12.     }  
13.   
14. }  
15.   
16. /* 
17. The Artition Function of Fast-typesetting in Introduction to Algorithms 
18. */  
19. int Partition(int *A,int low,int high)  
20. {  
21.     if(A==NULL || low<0 || high<0 || low>=high)  
22.         return -1;  
23.       
24.     int small = low-1;  
25.     int j;  
26.     for(j=low;j<high;j++)  
27.     {  
28.         if(A[j] <= A[high])  
29.         {  
30.             ++small;  
31.             if(j != small)  
32.                 Swap(&A[j],&A[small]);  
33.         }  
34.     }  
35.     ++small;  
36.     Swap(&A[small],&A[high]);  
37.     return small;  
38. }  
39.   
40. int Random_Partition(int *A,int low,int high)  
41. {  
42.     //Setting up random seeds  
43.     srand((unsigned)time(0));  
44.     int index = low + rand()%(high-low+1);  
45.     Swap(&A[index],&A[high]);  
46.     return Partition(A,low,high);  
47. }  
48.   
49.    
50. /* 
51. Returns more than half the number of occurrences in array A 
52. Implementation of Partition Function 
53. */  
54. void MinKNum(int *A,int len,int k)  
55. {  
56.     if(A==NULL || len<1)  
57.         return;  
58.   
59.     int low = 0;  
60.     int high = len-1;  
61.     int index = Random_Partition(A,low,high);  
62.     while(index != k-1)  
63.     {  
64.         if(index > k-1)  
65.             index = Random_Partition(A,low,index-1);  
66.         else  
67.             index = Random_Partition(A,index+1,high);  
68.     }  
69. }  
70.   
71. int main()  
72. {  
73.     int n,k;  
74.     while(scanf("%d %d",&n,&k) != EOF)  
75.     {  
76.         int *A = (int *)malloc(sizeof(int)*n);  
77.         if(A == NULL)  
78.             exit(EXIT_FAILURE);  
79.   
80.         int i;  
81.         for(i=0;i<n;i++)  
82.             scanf("%d",A+i);  
83.   
84.         MinKNum(A,n,k);  
85.         for(i=0;i<k;i++)  
86.         {  
87.             printf("%d ",A[i]);  
88.         }  
89.         printf("\n");  
90.     }  
91.     return 0;  
92. }  

3. Consider using small-top heap to build a small-top heap of n elements of an array, so that the smallest element is located on the top of the heap and exchanged with the last element of the array, so that the smallest element is saved in the last position of the array, and then adjust the n-1 in front by using the idea of heap sorting as well. Elements, so that they constitute a small top heap again, so that after K adjustments, the smallest k elements are stored in the last K positions of the array, and increase in turn from right to left.

In this method, it takes O(n) time to build a small top heap, and then filters out the minimum number of K times to adjust the heap. The time needed for each adjustment is O(logn), O (log (n-1), O (log (n-2)... O (log (n-k). It can be approximated that the time needed for each adjustment is O(logn). In this way, the time complexity of the method is O(n+klogn). As for the space complexity, if we can change the input array, we can directly build and adjust the heap on the array. This is the space complexity of O(1). If we can not change the input array, we need to build a small top heap, so the space complexity is O(n).

This method I used on 9OJ run s, resulting in AC, coded as follows:

    

1. #include<stdio.h>  
2. #include<stdlib.h>  
3.   
4. /* 
5. arr[start+1...end]Satisfying the definition of small-top heap, 
6. Add arr[start] to the small top heap arr[start+1...end], 
7. Adjust the position of arr[start] to make arr[start...end] a small top heap 
8. Note: Since the array is numbered from 0, that is, the root node of the binary heap is numbered 0. 
9. Therefore, the left and right sub-nodes with serial number I have serial numbers of 2i+1 and 2i+2, respectively. 
10. */  
11. void HeapAdjustDown(int *arr,int start,int end)  
12. {  
13.     int temp = arr[start];  //Save the current node  
14.     int i = 2*start+1;      //The position number of the left child of the node in the array  
15.     while(i<=end)  
16.     {  
17.         //Find out the youngest child in the right and left  
18.         if(i+1<=end && arr[i+1]<arr[i])    
19.             i++;  
20.         //If the heap definition is met, no position adjustment is required.  
21.         if(arr[i]>=temp)   
22.             break;  
23.         //The smallest child node moves up and replaces its parent node  
24.         arr[start] = arr[i];  
25.         start = i;  
26.         i = 2*start+1;  
27.     }  
28.     arr[start] = temp;  
29. }  
30.   
31. /* 
32. Get the smallest number of k and save the last k positions in arr 
33. */  
34. void MinHeapKNum(int *arr,int len,int k)  
35. {  
36.     if(arr==NULL || len<1 || k<1 || k>len)  
37.         return;  
38.   
39.     int i;  
40.     //Make the Data Group into a Small Top Heap  
41.     //The position number of the first non-leaf node is (len-1)/2.  
42.     for(i=(len-1)/2;i>=0;i--)  
43.         HeapAdjustDown(arr,i,len-1);  
44.     //Sort the heap  
45.     for(i=len-1;i>=len-k;i--)  
46.     {  
47.         //The top element and the last element exchange positions.  
48.         //So the last place is the smallest number.  
49.         //Each cycle places the next smallest value in front of it in turn.  
50.         int temp = arr[i];  
51.         arr[i] = arr[0];  
52.         arr[0] = temp;  
53.         //Re-adjust arr[0...i-1] to a small-top heap  
54.         HeapAdjustDown(arr,0,i-1);  
55.     }  
56. }  
57.   
58.   
59. int main()  
60. {  
61.     int n,k;  
62.     while(scanf("%d %d",&n,&k) != EOF)  
63.     {  
64.         int *A = (int *)malloc(sizeof(int)*n);  
65.         if(A == NULL)  
66.             exit(EXIT_FAILURE);  
67.   
68.         int i;  
69.         for(i=0;i<n;i++)  
70.             scanf("%d",A+i);  
71.   
72.         MinHeapKNum(A,n,k);  
73.         for(i=n-1;i>=n-k;i--)  
74.         {  
75.             //Output in required format  
76.             if(i == n-k)  
77.                 printf("%d\n",A[i]);  
78.             else  
79.                 printf("%d ",A[i]);  
80.         }  
81.     }  
82.     return 0;  
83. }  

4. Consider using large-top heap, but not using n elements of array to build heap, but using the first k numbers to build large-top heap, and then comparing the following n-k elements with the maximum (i.e. the top) elements in large-top heap in turn. If less than the maximum element, replace the top elements with this element. And adjust the heap to maintain the structure of the large-top heap. If it is larger than the maximum element, skip directly and continue to compare the next number with the top element. When all the elements are compared and operated, then the latter elements in the array are larger than the number in the large-top heap, then the K numbers in the large-top heap become the number. The smallest K number in the array, and the top element of the heap is the largest in the smallest K array, so it is the smallest K number in the array.

The time required to build a large top heap is O(k), and the time required to adjust the heap is O(logk) each time, and the total number of adjustments is n-k, so the time complexity is as follows:

O(k+(n-k)logk), when k is much less than n, the time complexity can be approximated to O(nlogk). In addition, this algorithm is very suitable for massive data processing, especially when the memory is limited and all data can not be read in one time, when n is large and K is small, k data can be read into memory at one time, and then one comparison can be read in each time, which can meet the requirements when the memory can hold up to K data.

5. The number of K can also be saved with an array (in fact, it can be abstracted as a container. Different container choices will have different effects on the required time). The maximum value can be obtained by comparing with the following elements. The strategy similar to the fourth method is used. Finally, the smallest number of K can be saved in the array. The time complexity of this method is O(n*k).

The above two ideas and codes are no longer given.