[已解决]给定数组，输出数值最大的前n个

秋木叶

算法复杂度 越高效越好

最佳答案

月排行榜 / 总排行榜

TOP_LK

2019-3-18 15:12:02

思路：1.判断n与数组长度len的大小，若n>len，返回false，若n==len，返回整个数组，否则执行下一步；
2.使用哨兵min记录数组前n个数中最小的数，从数组第n+1个元素开始遍历，判断每一个数tem与min的大小，若tem小于等于min，继续遍历，
否则，将tem与min互换，并重新计算min值，继续遍历数组直到结束。最后数组前n个数既是最大的前n个数。
整个过程只需遍历一边数组，时间消耗主要在当tem>min时，即需要找到前n个数中的最小值，可以使用最小堆，时间复杂度为O(log(n)),所以整个算法时间复杂度为O(len*log(n))

跳转到最佳答案楼层

TOP_LK

思路：1.判断n与数组长度len的大小，若n>len，返回false，若n==len，返回整个数组，否则执行下一步；
2.使用哨兵min记录数组前n个数中最小的数，从数组第n+1个元素开始遍历，判断每一个数tem与min的大小，若tem小于等于min，继续遍历，
否则，将tem与min互换，并重新计算min值，继续遍历数组直到结束。最后数组前n个数既是最大的前n个数。
整个过程只需遍历一边数组，时间消耗主要在当tem>min时，即需要找到前n个数中的最小值，可以使用最小堆，时间复杂度为O(log(n)),所以整个算法时间复杂度为O(len*log(n))

Croper

1. int* maxN(int* arr,int arrsize,int N) {
   
2.         int* ret = new int[N + 1];
   
3.         int cret = 0;
   
4.         for (int i = 0; i < arrsize; ++i) {
   
5.                 int num = arr[i];
   
6.                 int p = 0;
   
7.                 int q = cret;
   
8.                 while (p < q) {
   
9.                         int n = (p + q) / 2;
   
10.                         if (num <= ret[n]) p = n + 1;
    
11.                         else q = n;
    
12.                 }
    
13. 
    
14.                 for (int i = cret; i > q; --i) {
    
15.                         ret[i] = ret[i - 1];
    
16.                 }
    
17.                 ret[q] = num;
    
18.                 if (cret < N) ++cret;
    
19.         }
    
20. 
    
21.         return ret;
    
22. }
    

复制代码

时间复杂度O[arr.size*N]空间复杂度O[N]
插入部分改用链表时间复杂度可达到O[arr.size*log(N)]，但链表只有在数据量非常大时效率才较高，N较小时，链表效率不如直接数组

jackz007

     用 sort() 函数按从大到小排序，然后，取前 n 个即可

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. #include <time.h>
   
6. 
   
7. void random(int array[] , const int n)
   
8. {
   
9.         int c , k , m                             ;
   
10.         bool f                                    ;
    
11.         srand(time(0))                            ;
    
12.         for(k = 0 ; k < n ; k ++) array[k] = 0    ;
    
13.         m = 0                                     ;
    
14.         while(m < n) {
    
15.                 c = rand() % n + 1                ;
    
16.                 f = true                          ;
    
17.                 if (m) {
    
18.                         for(k = 0 ; k < m ; k ++) {
    
19.                                 if (array[k] == c) {
    
20.                                         f = false ;
    
21.                                         break     ;
    
22.                                 }
    
23.                         }
    
24.                 }
    
25.                 if (f) array[m ++] = c             ;
    
26.         }
    
27. }
    
28. 
    
29. void sort(int array[] , const int m)
    
30. {
    
31.         int d , i , j                           ;
    
32.         for(i = 1 ; i < m ; i ++) {
    
33.                 j = i                           ;
    
34.                 while(j > 0 && array[j - 1] < array[j]) {
    
35.                         d = array[j - 1]        ;
    
36.                         array[j - 1] = array[j] ;
    
37.                         array[j] = d            ;
    
38.                         j --                    ;
    
39.                 }
    
40.         }
    
41. }
    
42. 
    
43. main(void)
    
44. {
    
45.         int a[5000] , i , n                           ;
    
46.         random(a , 5000)                              ;
    
47.         n = 50                                        ;
    
48.         printf("%4d" , a[0])                          ;
    
49.         for(i = 1 ; i < n ; i ++) {
    
50.                 if(! (i % 10)) printf("\n%4d" , a[i]) ;
    
51.                 else printf(" , %4d" , a[i])          ;
    
52.         }
    
53.         printf("\n\n")                                ;
    
54.         sort(a , 5000)                                ;
    
55.         printf("%4d" , a[0])                          ;
    
56.         for(i = 1 ; i < n ; i ++) {
    
57.                 if(! (i % 10)) printf("\n%4d" , a[i]) ;
    
58.                 else printf(" , %4d" , a[i])          ;
    
59.         }
    
60.         printf("\n")                                  ;
    
61. }
    

复制代码

Croper

jackz007 发表于 2019-3-18 16:17
用 sort() 函数按从大到小排序，然后，取前 n 个即可

        下面是完整测试代码

但是光sort函数的时间复杂度已经不小于O[arr.size*log(arr.size)],因为在前N个之外的数据也一并排序了，执行了冗余的计算

秋木叶

Croper 发表于 2019-3-18 16:20
但是光sort函数的时间复杂度已经不小于O[arr.size*log(arr.size)],因为在前N个之外的数据也一并排序了， ...

这样的话和 冒泡排序 冒泡出前n 个元素后就停止排序，那个效率好点？

秋木叶

一道面试题， 我只想到了 冒泡排序 的改造，不知道 这样效率是不是最好的

Croper

秋木叶 发表于 2019-3-18 16:50
这样的话和 冒泡排序 冒泡出前n 个元素后就停止排序，那个效率好点？

思路是一样的，但冒泡排序本身就是一种效率比较低的排序。。。如果在长度为M的数组中使用冒泡排序冒N个元素，那么时间复杂度不会低于O[M*N]..
我的思路其实也是只排N个元素，在算法中，这N个元素永远是有序的，在插入新元素时，使用二分查找法。那么插入一个新元素的时间复杂度为O[log(N)],插入M个新元素的时间复杂度为O[M*log(N)],这样效率要高一些。。特别的，当M==N时，时间复杂度为O[N*log(N)]，符合一个理想排序算法的平均时间复杂度。
这种排序思路挺常用的。。。但是到底应该叫什么名字。。。把《数据结构与算法》内排序那一章翻完了好像也没找到到底该叫什么。。

jackz007

Croper 发表于 2019-3-18 16:20
但是光sort函数的时间复杂度已经不小于O[arr.size*log(arr.size)],因为在前N个之外的数据也一并排序了， ...

        下面这个 sort() 是严格按照要求取数组 array[] 中最大的前 n 个数放到前 n 个元素里，其余部分绝对维持原样。楼主再给测一测看效率如何？

1. void sort(int array[] , const int m  , const int n)
   
2. {
   
3.         int c , d , e , i , j                ;
   
4.         for(i = 0 ; i < n ; i ++) {
   
5.                 c = j = i                    ;
   
6.                 d = e = array[i]             ;
   
7.                 for(j = i + 1 ; j < m  ; j ++) {
   
8.                         if(array[j] > d) {
   
9.                                 d = array[j] ;
   
10.                                 c = j        ;
    
11.                         }
    
12.                 }
    
13.                 array[i] = d                 ;
    
14.                 array[c] = e                 ;
    
15.         }
    
16. }

复制代码

Croper

jackz007 发表于 2019-3-18 19:21
下面这个 sort() 是严格按照要求取数组 array[] 中最大的前 n 个数放到前 n 个元素里，其余部 ...

选择排序只排N个元素嘛
和我之前说的冒泡排序同样的问题，选择排序本身就是效率比较低的，这个算法时间复杂度不会小于O[M*N]..,如果真的要追求效率，那么肯定不能选用原始时间复杂度是O[N^2]的排序方法来改啊

82457097

我在书上看到过类似的 书上推荐的算法是 选取数组中第n个数作为基数 然后将数组中每个数与选取的基数比较 大的放左边 小的放右边 然后取选取基数的下标 如果大于n 说明最大的前n个数在左边 剔除左边下标减n个最小的数 反之同理 不过需要修改数组而且得到的数是无序的 因为这个算法没有排序过程 书上看到的 《剑指offer》

Croper

Croper 发表于 2019-3-18 16:04
时间复杂度O[arr.size*N]空间复杂度O[N]
插入部分改用链表时间复杂度可达到O[arr.size*log(N)]，但链表 ...

时间复杂度计算有误，如果使用list，并不能高效地使用二分查找，因此 时间复杂度仍然是O[M*N];

最好的方法应该是建立最大堆

1. #include <vector>
   
2. 
   
3. using namespace std;
   
4. 
   
5. class maxheap {
   
6. private:
   
7.         vector<int> nums;
   
8. 
   
9.         int adjustnode(int i) {
   
10.                 int maxpos = i;
    
11.                 int a = (i+1 << 1) -1;
    
12.                 if (a < nums.size() && nums[a]>nums[maxpos]) maxpos = a;
    
13.                 if (a+1 < nums.size() && nums[a+1]>nums[maxpos]) maxpos = a+1;
    
14.                 if (i != maxpos) {
    
15.                         int tmp = nums[maxpos];
    
16.                         nums[maxpos] = nums[i];
    
17.                         nums[i] = tmp;
    
18.                 }
    
19.                 return maxpos;
    
20.         }
    
21. public:
    
22.         maxheap(vector<int> input) {
    
23.                 nums = input;
    
24.                 for (int i = (nums.size() - 1 >> 1) - 1; i >= 0; --i) {
    
25.                         adjustnode(i);
    
26.                 }
    
27.         }
    
28. 
    
29.         int pop() {
    
30.                 int num = nums[0];
    
31.                 nums[0] = nums.back();
    
32.                 nums.pop_back();
    
33. 
    
34.                 int n = 0;
    
35.                 int m;
    
36.                 while (n != (m = adjustnode(n))) n = m;
    
37. 
    
38.                 return num;
    
39.         }
    
40. };
    
41. 
    
42. 
    
43. vector<int> maxN(vector<int> nums, int N) {
    
44.         maxheap h(nums);
    
45.         vector<int> ret;
    
46.         for (int i = 0; i < N; ++i)
    
47.                 ret.push_back(h.pop());
    
48.         return ret;
    
49. }

复制代码

时间复杂度O[N*log(M)]