C++实现的O(n)复杂度内查找第K大数算法示例
作者:叶赫那拉坤 发布时间:2023-06-30 15:51:13
标签:C++,查找,算法
本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法。分享给大家供大家参考,具体如下:
题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的三个数,最后输出最大乘积。
从题目我们知道只有两种结果存在:
1)三个最大的正整数相乘;
2)一个最大的正整数和两个最小的负数相乘。
所以我们需要找出数组中最大的三个数的乘积m,然后与数组中最小的两个数相乘再与最大的数相乘的结果n,然后比较m,n,选出最大的数即为最终的结果。
参考代码:https://www.jb51.net/article/121189.htm
实现代码:
#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
0
投稿
猜你喜欢
- 在windows环境下,我们通常在IDE如VS的工程中开发C++项目,对于生成和使用静态库(*.lib)与动态库(*.dll)可能都已经比较
- 对于大文件的处理,无论是用户端还是服务端,如果一次性进行读取发送、接收都是不可取,很容易导致内存问题。所以对于大文件上传,采用切块分段上传,
- 样例代码在讲 Flutter 的盒子模型前,先看看HTML 中的盒子模型。如下图所示,一个页面元素包括了与父级容器的外边距(margin),
- SingleClick:@Retention(AnnotationRetention.RUNTIME)@Target(AnnotationT
- ImageCacheconst int _kDefaultSize = 1000;const int _kDefaultSizeBytes
- mapper文件使用in("str1","str2")mybatis的xxxMapper.xml文件
- /// <summary> /// 遍历Co
- 前言这里主要简单介绍如何使用Camera+SurfaceView自定义相机拍照,如果是Camera2或者是TextureView的可以前往主
- 一、Monkey 是什么?Monkey 就是SDK中附带的一个工具。二、Monkey 测试的目的?:该工具用于进行压力测试。 然后开发人员结
- 目录多选和单选的不同之处实现方式界面变更代码实现总结多选和单选的不同之处单选的时候,选中一个就可以直接把结果返回,因此本身底部弹窗无需状态管
- 先看看效果Like This↓一、公共WiFi 公用电脑什么的在我们日常在线上工作、玩耍时,不论开电脑、登录淘宝、玩网游统统都会用到键盘输入
- 接收到这样一个需求,就是英文名字中firstName和lastName,其中任何一个为null,就返回Empty。刚拿到需求,这不简单,if
- iOS定位 - 普通定位(没有地图) - 反地理编码(得到具体位置),下面通过代码给大家详解,代码如下:#import <CoreLo
- 前言本文的记录如何用CustomPaint、GestureDetector实现一个进度条控件。首先需要说明的是 flutter Materi
- mport java.text.DecimalFormat; DecimalFormat &nb
- 本文实例为大家分享了android实现简易计算器展示的具体代码,供大家参考,具体内容如下效果图:一、如图,首先布局计算器主页显示activi
- BitArray的基础可以看菜鸟编程BitArray 类管理一个紧凑型的位值数组,它使用布尔值来表示,其中 true 表示位是开启的(1),
- Spring JPA 增加字段执行异常用Spring jpa Entity里面增加了几个字段,但启动报错,提示column Unable t
- 概述:App几乎都离不开与服务器的交互,本文主要讲解了flutter网络请求三种方式 flutter自带的HttpClient、 第三方库h
- 一、目的本篇文章的目的是记录本人使用flutter加载与调用第三方aar包。二、背景本人go后端,业余时间喜欢玩玩flutter。一直有一个