本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法。分享给大家供大家参考,具体如下:
题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的三个数,最后输出最大乘积。
从题目我们知道只有两种结果存在:
1)三个最大的正整数相乘;
2)一个最大的正整数和两个最小的负数相乘。
所以我们需要找出数组中最大的三个数的乘积m,然后与数组中最小的两个数相乘再与最大的数相乘的结果n,然后比较m,n,选出最大的数即为最终的结果。
参考代码:http://www.zzvips.com/article/166833.html
实现代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
#include <iostream>
#include <algorithm>
//分区
int partition(std::vector< int >&vec, int start, int end) {
int value=vec[end];
int tail=start-1;
for ( int i=start;i<end;++i){
if (vec[i]<value){
tail++;
std::swap(vec[i],vec[tail]);
}
}
tail++;
std::swap(vec[tail],vec[end]);
return tail;
}
long long solve(std::vector< int >&vec, int start, int end, int k) {
//快排思想,进行分区,快排复杂度为O(nlgn),但取最值只比较分区的一个区间,所以为O(n)
int now = partition(vec,start,end);
if (k < now)
return solve(vec,start,now-1,k);
else if (k > now)
return solve(vec,now+1,end,k);
else
return vec[now];
}
int main() {
int n; //要比较的数的个数
while (std::cin>>n) {
std::vector< int > vec_i(n,0); //使用vector存储n个数
for ( int i = 0; i < n; ++i) {
std::cin>>vec_i[i];
}
int k;
//最大的数,index为n-1
k = n - 1;
long long x1 = solve(vec_i,0, n-1,k);
//次大的数,index为n-2
k = n - 2;
long long x2 = solve(vec_i,0, n-2,k);
//第三大的数
k = n - 3;
long long x3 = solve(vec_i,0, n-3,k);
long long Ans = x1 * x2 * x3; //最大的三个数的乘积
if (n > 3) {
//最小的数,index为0
k = 0;
long long y1 = solve(vec_i,0, n-1,k);
//次小的数,index为1
k = 1;
long long y2 = solve(vec_i,0, n-2,k);
Ans = std::max(Ans, y1*y2*x1); //两者比较取最大
}
std::cout<<Ans;
}
return 0;
}
|
希望本文所述对大家C++程序设计有所帮助。
原文链接:http://blog.csdn.net/u010558281/article/details/76572832