C++实现的O(n)复杂度内查找第K大数算法示例

本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法。分享给大家供大家参考，具体如下：

题目：是在一组数组（数组元素为整数，可正可负可为0）中查找乘积最大的三个数，最后输出最大乘积。

从题目我们知道只有两种结果存在：
1）三个最大的正整数相乘；
2）一个最大的正整数和两个最小的负数相乘。

所以我们需要找出数组中最大的三个数的乘积m，然后与数组中最小的两个数相乘再与最大的数相乘的结果n，然后比较m,n，选出最大的数即为最终的结果。

参考代码：http://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++程序设计有所帮助。

赞 (0)

相关推荐

  • c++ 快速排序算法【过程图解】

    c++ 快速排序算法【过程图解】

    第一.算法描述 快速排序由C. A. R. Hoare在1962年提出,该算法是目前实践中使用最频繁,实用高效的最好排序算法, 快速排序算法是采用分治思想的算法,算法分三个步骤 1.从数组中抽出一个元素作为基数v(我们称之为划界元素),一般是取第一个.最后一个元素或中间的元素 2.将剩余的元素中小于v的移动到v的左边,将大于v元素移动到v的右边 3.对左右两个分区重复以上步骤直到所有元素都是有排序好. 第二.算法实现 /*序列划分函数*/ int partition(int a[], int p

  • C++二分查找(折半查找)算法实例详解

    本文实例讲述了C++二分查找(折半查找)算法.分享给大家供大家参考,具体如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难. 因此,折半查找方法适用于不经常变动而查找频繁的有序列表. 二分查找思想 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功: 否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 重复

  • C++ 搬水果贪心算法实现代码

    C++ 搬水果贪心算法实现代码 (1)题目描述: 在一个果园里,小明已经将所有的水果打了下来,并按水果的不同种类分成了若干堆,小明决定把所有的水果合成一堆.每一次合并,小明可以把两堆水果合并到一起,消耗的体力等于两堆水果的重量之和.当然经过 n‐1 次合并之后,就变成一堆了.小明在合并水果时总共消耗的体力等于每次合并所耗体力之和. 假定每个水果重量都为 1,并且已知水果的种类数和每种水果的数目,你的任务是设计出合并的次序方案,使小明耗费的体力最少,并输出这个最小的体力耗费值.例如有 3 种水果,

  • C++实现的大数相乘算法示例

    本文实例讲述了C++实现的大数相乘算法.分享给大家供大家参考,具体如下: 昨晚校招笔试,虐的没脸睡觉,能力太渣了,但我还在码农的坑里前行,希望早日跳坑,解决衣食住行之忧. 大数相乘,是指那些相乘结果或是乘数本身用long long类型都会溢出的数字,通常这些数字都通过string类型进行表示,借助于可动态调整大小的数据结构(vector,string,deque)模拟实现数字的乘法操作.对于普通的乘法,我们知道m位数和n位数相乘,最后的结果位数在区间内[m+n-1,m+n].例如34*56,我们

  • C++实现的归并排序算法详解

    本文实例讲述了C++实现的归并排序算法.分享给大家供大家参考,具体如下: 归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列: 即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 1.比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到temp[k]中,并令i

  • C++实现迷宫算法实例解析

    本文以实例形式描述了C++实现迷宫算法.本例中的迷宫是一个矩形区域,它有一个入口和一个出口.在迷宫的内部包含不能穿越的墙或障碍.障碍物沿着行和列放置,它们与迷宫的矩形边界平行.迷宫的入口在左上角,出口在右下角 本实例迷宫算法的功能主要有: 1.自动生成10*10迷宫图 2.判断是否有迷宫出口,并且画出路线图 具体实现代码如下: # include <iostream> # include <list> # include <sys/timeb.h> # include

  • C++使用递归函数和栈操作逆序一个栈的算法示例

    本文实例讲述了C++使用递归函数和栈操作逆序一个栈的算法.分享给大家供大家参考,具体如下: 题目: 一个栈依次压入1.2.3.4.5,那么栈顶到栈底分别为:5.4.3.2.1. 将这个栈逆置后栈顶到栈底分别为1.2.3.4.5. 用递归函数来实现,不能用其他数据结构. 解题思路及代码 1.递归函数一:将栈的栈底元素一个个返回并移除. 2.递归函数二:逆序栈,调用递归函数一实现. C++实现: class Solution { public: //递归函数一 static int getAndRe

  • 基于C++的拼多多算法在线笔试题示例

    本文实例讲述了基于C++的拼多多算法在线笔试题.分享给大家供大家参考,具体如下: 最近在狼厂实习中,很久没做题了.秋招第一发, 拼多多...  四个简单题,看到有些人竟然觉得难? 我来降一发自己的RP,这题目觉得难的,如果你拿到比我好的Offer,我是不服气的.. 四个题...其实我也就写了40分钟吧..不过最后也没有满分, 390/400, 第三题不知道为嘛一直有10分过不了.. 更一下, 刚刚好像发现第三题...这个>号, 我写的是>= ....? 可是我看题目好像是 >= 呀...

  • C++使用一个栈实现另一个栈的排序算法示例

    本文实例讲述了C++用一个栈实现另一个栈的排序算法.分享给大家供大家参考,具体如下: 题目: 一个栈中元素类型为整型,现在想将该栈从顶到底按从小到大的顺序排序,只许申请一个辅助栈. 除此之外,可以申请新的变量,但不能申请额外的数据结构.如何完成排序? 算法C++代码: class Solution { public: //借助一个临时栈排序源栈 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp =

  • C++实现的O(n)复杂度内查找第K大数算法示例

    本文实例讲述了C++实现的O(n)复杂度内查找第K大数算法.分享给大家供大家参考,具体如下: 题目:是在一组数组(数组元素为整数,可正可负可为0)中查找乘积最大的三个数,最后输出最大乘积. 从题目我们知道只有两种结果存在: 1)三个最大的正整数相乘: 2)一个最大的正整数和两个最小的负数相乘. 所以我们需要找出数组中最大的三个数的乘积m,然后与数组中最小的两个数相乘再与最大的数相乘的结果n,然后比较m,n,选出最大的数即为最终的结果. 参考代码:http://www.jb51.net/artic

  • 通过Mybatis实现单表内一对多的数据展示示例代码

    通过Mybatis实现单表内一对多的数据展示示例代码

    表: 需求: 将表中的数据,按照一级二级分类返回给前端json数据 代码实现: java代码: public class ResultIndustry { private String industryFirst;//一级行业 private List<String> industrySecondList;//二级行业 mybatis代码: <select id="getResultIndustryList" resultMap="resultIndustr

  • Vue 内置组件keep-alive的使用示例

    目录 一.keep-alive 用法 使用示例: 1.缓存所有页面: 2.根据条件缓存部分页面 3.结合vue-router,缓存部分页面 二.keep-alive 生命周期 1. activated 2. deactivated keep-alive 是Vue内置的组件之一, 主要用于保留组件状态或避免重新渲染. 作用    在组件切换过程中将状态保留在内存中,防止重复渲染DOM,减少加载时间及性能消耗,提高用户体验. 一.keep-alive 用法 < keep-alive> 包裹动态组件

  • nginx中封禁ip和允许内网ip访问的实现示例

    目录 一.语法 二.封禁ip 三.仅内网IP访问 Nginx不仅仅只是一款反向代理和负载均衡服务器,它还能提供很多强大的功能,例如:限流.缓存.黑白名单和灰度发布等等,我们先来了解一下nginx如何封禁ip和允许内网ip访问. 一.语法 Nginx的ngx_http_access_module 模块可以封配置内的ip或者ip段 deny IP; deny subnet; allow IP; allow subnet; # block all ips deny all; # allow all i

  • 手写Vue内置组件component的实现示例

    手写Vue内置组件component的实现示例

    目录 前言 内置组件component的使用 component组件的原理分析 虚拟DOM与原生DOM render函数的使用 尝试手写实现component 总结 最近在复习Vue的源码,今天带大家手写实现一下Vue内置组件component,比较简单,最近面试有被问到. 前言 Vue大家都很熟悉,除了原生的组件,其自己也封装了一下内置组件,比如component,transition,keep-alive等等. component算是用的比较多的了,当我们遇到需要根据不同条件显示不同组件的时

  • php+redis实现多台服务器内网存储session并读取示例

    大型网站由于大并发的问题会导致系统出现诡异的崩溃性问题这着实让人很是蛋疼,首先考虑的就是负载均衡服务器来处理这个,当然数据库的性能也是非常非常重要的,今天就说下在负载均衡情况下对于session这个问题如何处理,说实话不处理session其实也是可以的,但是在实际的情况中会出现一些让用户体验非常蛋疼的问题,比如购物下单的时候负载均衡调配服务器来回切换的过程中session丢失了,这个时候就尴尬了,用户就会郁闷我擦这什么鬼,于是乎各种担心就会出现,这破网站是不是有什么安全问题等等.下面就来说说这个

  • jquery内置验证(validate)使用方法示例(表单验证)

    (1)required:true 必输字段(2)remote:"check.php" 使用ajax方法调用check.php验证输入值(3)email:true 必须输入正确格式的电子邮件(4)url:true 必须输入正确格式的网址(5)date:true 必须输入正确格式的日期(6)dateISO:true 必须输入正确格式的日期(ISO),例如:2009-06-23,1998/01/22 只验证格式,不验证有效性(7)number:true 必须输入合法的数字(负数,小数)(8)

  • Java基于余弦方法实现的计算相似度算法示例

    本文实例讲述了Java基于余弦方法实现的计算相似度算法.分享给大家供大家参考,具体如下: (1)余弦相似性 通过测量两个向量之间的角的余弦值来度量它们之间的相似性.0度角的余弦值是1,而其他任何角度的余弦值都不大于1;并且其最小值是-1.从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向.所以,它通常用于文件比较. 相关介绍可参考百度百科:余弦相似性 (2)算法实现的中未使用权重(IDF ---逆文档频率),使用词项的出现次数作为向量空间的值. import java.util.H

  • PHP数据分析引擎计算余弦相似度算法示例

    本文实例讲述了PHP数据分析引擎计算余弦相似度算法.分享给大家供大家参考,具体如下: 关于余弦相似度的相关介绍可参考百度百科:余弦相似度 <?php /** * 数据分析引擎 * 分析向量的元素 必须和基准向量的元素一致,取最大个数,分析向量不足元素以0填补. * 求出分析向量与基准向量的余弦值 * @author yu.guo@okhqb.com */ /** * 获得向量的模 * @param unknown_type $array 传入分析数据的基准点的N维向量.|eg:array(1,1

  • C#编程实现统计文件夹内文件和隐藏文件的方法示例

    C#编程实现统计文件夹内文件和隐藏文件的方法示例

    本文实例讲述了C#编程实现统计文件夹内文件和隐藏文件的方法.分享给大家供大家参考,具体如下: C#统计文件夹内的文件,包括隐藏文件,显示那个隐藏文件...隐藏的..为什么别人要隐藏呢.. 将程序放在任何文件夹内,点击"当前文件夹",可以获取文件夹所在的路径,也可以直接输入路径,再点击"显示文件",就可以看到效果了,下面的状态栏实现统计功能 using System; using System.Collections.Generic; using System.Co

随机推荐