深入线性时间复杂度求数组中第K大数的方法详解

求数组中第K大的数可以基于快排序思想，步骤如下：
1、随机选择一个支点
2、将比支点大的数，放到数组左边；将比支点小的数放到数组右边；将支点放到中间(属于左部分)
3、设左部分的长度为L，
当K < L时，递归地在左部分找第K大的数
当K > L时，递归地在有部分中找第(K - L)大的数
当K = L时，返回左右两部分的分割点（即原来的支点），就是要求的第K大的数
以上思想的代码实现如下：


代码如下:

/**
线性时间复杂度求数组中第K大数
** author :liuzhiwei
** data   :2011-08-07 
**/
#include "iostream"
using namespace std;
//基于快速排序思想，求数组a中第k大的数，low和high分别为数组的起始和结束位置
//时间复杂度为o(n)，n为数组的长度
//1<=k<=n
//如果存在，返回第k大数的下标，否则返回-1
int selectk(int a[], int low, int high, int k)
{
 if(k <= 0)
  return -1;
 if(k > high - low + 1)
  return -1;
 int pivot = low + rand()%(high - low + 1);    //随即选择一个支点
 swap(a[low], a[pivot]);
 int m = low;
 int count = 1;
 //一趟遍历，把较大的数放到数组的左边
 for(int i = low + 1; i <= high; ++i)
 {
  if(a[i] > a[low])
  {
   swap(a[++m], a[i]);
   count++;              //比支点大的数的个数为count-1
  }
 }
 swap(a[m], a[low]);           //将支点放在左、右两部分的分界处
 if(count > k)
 {
  return selectk(a, low, m - 1, k);
 }
 else if( count < k)
 {
  return selectk(a, m + 1, high, k - count);
 }
 else
 {
  return m;
 }
}
int main(void)
{
 int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
 int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 5);
 cout<<(r == -1 ? r : a[r])<<endl;
 system("pause");
 return 0;
}

稍微改动一下，就可以修改为求数组中第K小数
完整的代码如下：


代码如下:

/**
线性时间复杂度求数组中第K小数
** author :liuzhiwei
** data   :2011-08-07 
**/
#include "iostream"
using namespace std;
//基于快速排序思想，求数组a中第k小的数，low和high分别为数组的起始和结束位置
//时间复杂度为o(n)，n为数组的长度
//1<=k<=n
//如果存在，返回第k小数的下标，否则返回-1
int selectk(int a[], int low, int high, int k)
{
 if(k <= 0)
  return -1;
 if(k > high - low + 1)
  return -1;
 int pivot = low + rand()%(high - low + 1);    //随即选择一个支点
 swap(a[low], a[pivot]);
 int m = low;
 int count = 1;
 //一趟遍历，把较小的数放到数组的左边
 for(int i = low + 1; i <= high; ++i)
 {
  if(a[i]<a[low])
  {
   swap(a[++m], a[i]);
   count++;              //比支点小的数的个数为count-1
  }
 }
 swap(a[m], a[low]);           //将支点放在左、右两部分的分界处
 if(k < count)
 {
  return selectk(a, low, m - 1, k);
 }
 else if( k > count)
 {
  return selectk(a, m + 1, high, k - count);
 }
 else
 {
  return m;
 }
}
int main(void)
{
 int a[] = {5, 15, 5, 7, 9, 17,100, 3, 12, 10, 19, 18, 16, 10, 1000,1,1,1,1,1,1,1,1};
 int r = selectk(a, 0, sizeof(a) /sizeof(int) - 1, 23);
 cout<<(r == -1 ? r : a[r])<<endl;
 system("pause");
 return 0;
}

赞 (0)

相关推荐

  • 深入第K大数问题以及算法概要的详解

    解法1: 我们可以对这个乱序数组按照从大到小先行排序,然后取出前k大,总的时间复杂度为O(n*logn + k). 解法2: 利用选择排序或交互排序,K次选择后即可得到第k大的数.总的时间复杂度为O(n*k) 解法3: 利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb.Sa中的元素大于等于X,Sb中元素小于X.这时有两种情况:1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数:2. Sa中元素的个数大于等于k,则返回Sa中的第k大数.时间复杂度近

  • C#递归算法寻找数组中第K大的数

    1.概述 国人向来喜欢论资排辈的,每个人都想当老大,实在当不成,当个老二,老三,老K也不错,您一定看过这样的争论: 两个人吵架,一个人非常强势,另外一个忍受不住了便说:"你算老几呀?",下面就通过这篇文章就是要解决找出老几的问题! 2.应用场景 在向量V[first,last)中查找出第K大元素的值 3.分析 如果利用排序算法将向量V排好序,那么第K大元素就是索引为v.length-k的元素了,这样能解决问题,但效率不高,因为这相当于为了歼灭敌人一个小队而动用了我们全军的力量,得不偿失

  • 数组中求第K大数的实现方法

    问题:有一个大小为n的数组A[0,1,2,-,n-1],求其中第k大的数.该问题是一个经典的问题,在<算法导论>中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们的意料,此处暂且不表.该问题还可以变形为:有一个大小为 n的数组A[0,1,2,-,n-1],求其中前k大的数.一字之差,原问题是"第k大",变形的问题是"前k大",但是平均时间复杂度却都可以控制在O(n),这不由得让人暗暗称奇. 我们先分

  • 深入线性时间复杂度求数组中第K大数的方法详解

    求数组中第K大的数可以基于快排序思想,步骤如下:1.随机选择一个支点2.将比支点大的数,放到数组左边:将比支点小的数放到数组右边:将支点放到中间(属于左部分)3.设左部分的长度为L,当K < L时,递归地在左部分找第K大的数当K > L时,递归地在有部分中找第(K - L)大的数当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数以上思想的代码实现如下: 复制代码 代码如下: /**线性时间复杂度求数组中第K大数** author :liuzhiwei ** data 

  • numpy中三维数组中加入元素后的位置详解

    今天做数据处理时,遇到了从三维数组中批量加入二维数组的需求.其中三维数组在深度学习的特征数据处理时经常会使用到,所以读者有必要对该小知识点做到清楚了解并掌握.现对三维数组中的元素位置结合代码做详细归纳总结,方便日后查阅和为网友答疑! 图示效果图: 直接贴代码: def test3D(): import numpy as np data_array = np.zeros((3, 5, 6), dtype=np.int) data_array[1, 2, 2] = 1 print(data_arra

  • JavaScript中数组去重常用的五种方法详解

    目录 1.对象属性(indexof) 2.new Set(数组) 3.new Map() 4.filter() + indexof 5.reduce() + includes 补充 原数组 const arr = [1, 1, '1', 17, true, true, false, false, 'true', 'a', {}, {}]; 1.对象属性(indexof) 利用对象属性key排除重复项 遍历数组,每次判断新数组中是否存在该属性,不存在就存储在新数组中 并把数组元素作为key,最后返

  • Javascript中的迭代、归并方法详解

    迭代方法 在Javascript中迭代方法个人觉得尤为重要,在很多时候都会有实际上的需求,javascript提供了5个迭代方法来供我们操作,它们分别为: every() 对数组中的每一个项运用给定的函数,如果每项都返回true,那么就会返回true filter() 对数组中的每一个项运用给定的函数,把返回true的项组成一个新数组并返回 forEach() 对数组中的每一项运用给定的函数,但是没有任何的返回值 map() 对数组中的每一个项运用给定的函数并返回每次函数调用的结果组成新的数组

  • js基础之DOM中元素对象的属性方法详解

    js基础之DOM中元素对象的属性方法详解

    在 HTML DOM (文档对象模型)中,每个部分都是节点. 节点是DOM结构中最基本的组成单元,每一个HTML标签都是DOM结构的节点. 文档是一个    文档节点 . 所有的HTML元素都是    元素节点 所有 HTML 属性都是    属性节点 文本插入到 HTML 元素是    文本节点 注释是    注释节点. 最基本的节点类型是Node类型,其他所有类型都继承自Node,DOM操作往往是js中开销最大的部分,因而NodeList导致的问题最多.要注意:NodeList是'动态的',

  • JavaScript中关键字 in 的使用方法详解

    for-in循环应该用在非数组对象的遍历上,使用for-in进行循环也被称为"枚举". 对于数组 ,迭代出来的是数组元素 但不推荐,因为不能保证顺序,而且如果在Array的原型上添加了属性,这个属性也会被遍历出来,所以 最好数组使用正常的for循环,对象使用for-in循环 对于对象 ,迭代出来的是对象的属性: var obj = { "key1":"value1", "key2":"value2", &q

  • struts2中使用注解配置Action方法详解

    使用注解来配置Action可以实现零配置,零配置将从基于纯XML的配置转化为基于注解的配置.使用注解,可以在大多数情况下避免使用struts.xml文件来进行配置. struts2框架提供了四个与Action相关的注解类型,分别为ParentPackage.Namespace.Result和Action. ParentPackage:ParentPackage注解用于指定Action所在的包要继承的父包.该注解只有一个value参数.用于指定要继承的父包. 示例: 使用ParentPackage

  • python更新数据库中某个字段的数据(方法详解)

    连接数据库基本操作,我把每一步的操作是为什么给大家注释一下,老手自行快进. 请注意这是连接数据库操作,还不是更新. import pymysql #导包 #连接数据库 db = pymysql.connect(host='localhost', user='用户名', password='数据库密码', port=3306, db='你的数据库名字') #定义游标 cursor = db.cursor() #sql语句 sql = 'select * from students;' cursor

  • Spring中bean集合注入的方法详解

    Spring中bean集合注入的方法详解

    目录 Map注入 List注入 Set注入 数组注入 应用 哈喽大家好啊,我是Hydra. Spring作为项目中不可缺少的底层框架,提供的最基础的功能就是bean的管理了.bean的注入相信大家都比较熟悉了,但是有几种不太常用到的集合注入方式,可能有的同学会不太了解,今天我们就通过实例看看它的使用. 首先,声明一个接口: public interface UserDao { String getName(); } 然后定义两个类来分别实现这个接口,并通过@Component注解把bean放入s

  • 在C#程序中注入恶意DLL的方法详解

    在C#程序中注入恶意DLL的方法详解

    目录 一.背景 二.实现原理 1. 基本思路 2. 案例演示 3. 自定义注入 三:总结 一.背景 前段时间在训练营上课的时候就有朋友提到一个问题,为什么 Windbg 附加到 C# 程序后,程序就处于中断状态了?它到底是如何实现的?其实简而言之就是线程的远程注入,这一篇就展开说一下. 二.实现原理 1. 基本思路 WinDbg 在附加进程的时候,会注入一个线程到 C# 进程 中,注入成功后,会执行一个 DbgBreakPoint() 函数,其实就是 int 3 ,这时候 CPU 就会执行 3

随机推荐