给定数组，输出数值最大的前n个
算法复杂度 越高效越好 思路：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 于 2019-3-18 16:09 编辑
int* maxN(int* arr,int arrsize,int N) {
int* ret = new int;
int cret = 0;
for (int i = 0; i < arrsize; ++i) {
int num = arr;
int p = 0;
int q = cret;
while (p < q) {
int n = (p + q) / 2;
if (num <= ret) p = n + 1;
else q = n;
}
for (int i = cret; i > q; --i) {
ret = ret;
}
ret = num;
if (cret < N) ++cret;
}
return ret;
}
时间复杂度O空间复杂度O
插入部分改用链表时间复杂度可达到O，但链表只有在数据量非常大时效率才较高，N较小时，链表效率不如直接数组 本帖最后由 jackz007 于 2019-3-18 16:22 编辑
用 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 = 0 ;
m = 0 ;
while(m < n) {
c = rand() % n + 1 ;
f = true ;
if (m) {
for(k = 0 ; k < m ; k ++) {
if (array == c) {
f = false ;
break ;
}
}
}
if (f) array = c ;
}
}
void sort(int array[] , const int m)
{
int d , i , j ;
for(i = 1 ; i < m ; i ++) {
j = i ;
while(j > 0 && array < array) {
d = array ;
array = array ;
array = d ;
j -- ;
}
}
}
main(void)
{
int a , i , n ;
random(a , 5000) ;
n = 50 ;
printf("%4d" , a) ;
for(i = 1 ; i < n ; i ++) {
if(! (i % 10)) printf("\n%4d" , a) ;
else printf(" , %4d" , a) ;
}
printf("\n\n") ;
sort(a , 5000) ;
printf("%4d" , a) ;
for(i = 1 ; i < n ; i ++) {
if(! (i % 10)) printf("\n%4d" , a) ;
else printf(" , %4d" , a) ;
}
printf("\n") ;
}
jackz007 发表于 2019-3-18 16:17
用 sort() 函数按从大到小排序，然后，取前 n 个即可
下面是完整测试代码
但是光sort函数的时间复杂度已经不小于O,因为在前N个之外的数据也一并排序了，执行了冗余的计算 Croper 发表于 2019-3-18 16:20
但是光sort函数的时间复杂度已经不小于O,因为在前N个之外的数据也一并排序了， ...
这样的话和 冒泡排序 冒泡出前n 个元素后就停止排序，那个效率好点？ 一道面试题， 我只想到了 冒泡排序 的改造，不知道 这样效率是不是最好的 秋木叶 发表于 2019-3-18 16:50
这样的话和 冒泡排序 冒泡出前n 个元素后就停止排序，那个效率好点？
思路是一样的，但冒泡排序本身就是一种效率比较低的排序。。。如果在长度为M的数组中使用冒泡排序冒N个元素，那么时间复杂度不会低于O..
我的思路其实也是只排N个元素，在算法中，这N个元素永远是有序的，在插入新元素时，使用二分查找法。那么插入一个新元素的时间复杂度为O,插入M个新元素的时间复杂度为O,这样效率要高一些。。特别的，当M==N时，时间复杂度为O，符合一个理想排序算法的平均时间复杂度。
这种排序思路挺常用的。。。但是到底应该叫什么名字。。。把《数据结构与算法》内排序那一章翻完了好像也没找到到底该叫什么。。 本帖最后由 jackz007 于 2019-3-18 19:22 编辑
Croper 发表于 2019-3-18 16:20
但是光sort函数的时间复杂度已经不小于O,因为在前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 ;
for(j = i + 1 ; j < m; j ++) {
if(array > d) {
d = array ;
c = j ;
}
}
array = d ;
array = e ;
}
} jackz007 发表于 2019-3-18 19:21
下面这个 sort() 是严格按照要求取数组 array[] 中最大的前 n 个数放到前 n 个元素里，其余部 ...
选择排序只排N个元素嘛
和我之前说的冒泡排序同样的问题，选择排序本身就是效率比较低的，这个算法时间复杂度不会小于O..,如果真的要追求效率，那么肯定不能选用原始时间复杂度是O的排序方法来改啊 我在书上看到过类似的 书上推荐的算法是 选取数组中第n个数作为基数 然后将数组中每个数与选取的基数比较 大的放左边 小的放右边 然后取选取基数的下标 如果大于n 说明最大的前n个数在左边 剔除左边下标减n个最小的数 反之同理 不过需要修改数组而且得到的数是无序的 因为这个算法没有排序过程 书上看到的 《剑指offer》 Croper 发表于 2019-3-18 16:04
时间复杂度O空间复杂度O
插入部分改用链表时间复杂度可达到O，但链表 ...
时间复杂度计算有误，如果使用list，并不能高效地使用二分查找，因此 时间复杂度仍然是O;
最好的方法应该是建立最大堆#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>nums) maxpos = a;
if (a+1 < nums.size() && nums>nums) maxpos = a+1;
if (i != maxpos) {
int tmp = nums;
nums = nums;
nums = 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;
nums = 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
页:
[1]