[已解决]给定数组，输出数值最大的前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

int* maxN(int* arr,int arrsize,int N) {
        int* ret = new int[N + 1];
        int cret = 0;
        for (int i = 0; i < arrsize; ++i) {
                int num = arr[i];
                int p = 0;
                int q = cret;
                while (p < q) {
                        int n = (p + q) / 2;
                        if (num <= ret[n]) p = n + 1;
                        else q = n;
                }

                for (int i = cret; i > q; --i) {
                        ret[i] = ret[i - 1];
                }
                ret[q] = num;
                if (cret < N) ++cret;
        }

        return ret;
}

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

jackz007

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <time.h>

void random(int array[] , const int n)
{
        int c , k , m                             ;
        bool f                                    ;
        srand(time(0))                            ;
        for(k = 0 ; k < n ; k ++) array[k] = 0    ;
        m = 0                                     ;
        while(m < n) {
                c = rand() % n + 1                ;
                f = true                          ;
                if (m) {
                        for(k = 0 ; k < m ; k ++) {
                                if (array[k] == c) {
                                        f = false ;
                                        break     ;
                                }
                        }
                }
                if (f) array[m ++] = c             ;
        }
}

void sort(int array[] , const int m)
{
        int d , i , j                           ;
        for(i = 1 ; i < m ; i ++) {
                j = i                           ;
                while(j > 0 && array[j - 1] < array[j]) {
                        d = array[j - 1]        ;
                        array[j - 1] = array[j] ;
                        array[j] = d            ;
                        j --                    ;
                }
        }
}

main(void)
{
        int a[5000] , i , n                           ;
        random(a , 5000)                              ;
        n = 50                                        ;
        printf("%4d" , a[0])                          ;
        for(i = 1 ; i < n ; i ++) {
                if(! (i % 10)) printf("\n%4d" , a[i]) ;
                else printf(" , %4d" , a[i])          ;
        }
        printf("\n\n")                                ;
        sort(a , 5000)                                ;
        printf("%4d" , a[0])                          ;
        for(i = 1 ; i < n ; i ++) {
                if(! (i % 10)) printf("\n%4d" , a[i]) ;
                else printf(" , %4d" , a[i])          ;
        }
        printf("\n")                                  ;
}

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 个元素里，其余部分绝对维持原样。楼主再给测一测看效率如何？

void sort(int array[] , const int m  , const int n)
{
        int c , d , e , i , j                ;
        for(i = 0 ; i < n ; i ++) {
                c = j = i                    ;
                d = e = array[i]             ;
                for(j = i + 1 ; j < m  ; j ++) {
                        if(array[j] > d) {
                                d = array[j] ;
                                c = j        ;
                        }
                }
                array[i] = d                 ;
                array[c] = e                 ;
        }
}

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];

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

#include <vector>

using namespace std;

class maxheap {
private:
        vector<int> nums;

        int adjustnode(int i) {
                int maxpos = i;
                int a = (i+1 << 1) -1;
                if (a < nums.size() && nums[a]>nums[maxpos]) maxpos = a;
                if (a+1 < nums.size() && nums[a+1]>nums[maxpos]) maxpos = a+1;
                if (i != maxpos) {
                        int tmp = nums[maxpos];
                        nums[maxpos] = nums[i];
                        nums[i] = tmp;
                }
                return maxpos;
        }
public:
        maxheap(vector<int> input) {
                nums = input;
                for (int i = (nums.size() - 1 >> 1) - 1; i >= 0; --i) {
                        adjustnode(i);
                }
        }

        int pop() {
                int num = nums[0];
                nums[0] = nums.back();
                nums.pop_back();

                int n = 0;
                int m;
                while (n != (m = adjustnode(n))) n = m;

                return num;
        }
};


vector<int> maxN(vector<int> nums, int N) {
        maxheap h(nums);
        vector<int> ret;
        for (int i = 0; i < N; ++i)
                ret.push_back(h.pop());
        return ret;
}

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