深入第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大数。时间复杂度近似为O(n)

解法4： 二分[Smin,Smax]查找结果X，统计X在数组中出现，且整个数组中比X大的数目为k-1的数即为第k大数。时间复杂度平均情况为O(n*logn)

解法5：用O(4*n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4*n + k*logn)

解法6：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)

解法7：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)

赞 (0)

相关推荐

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

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

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

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

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

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

  • 深入第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大数.时间复杂度近

  • Go Java算法之K个重复字符最长子串详解

    目录 至少有K个重复字符的最长子串 方法一:分治(Java) 方法二:滑动窗口(go) 至少有K个重复字符的最长子串 给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串, 要求该子串中的每一字符出现次数都不少于 k .返回这一子串的长度. 示例 1: 输入:s = "aaabb", k = 3 输出:3 解释:最长子串为 "aaa" ,其中 'a' 重复了 3 次. 示例 2: 输入:s = "ababbc", k = 2 输出:5

  • java 算法之归并排序详解及实现代码

    java 算法之归并排序详解 一.思想 归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来: 二.概念 归并:将两个有序的数组归并成一个更大的有序数组: 三.特点 优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比: 缺点:需要额外的空间和N成正比: 四.实现方法 将两个不同的有序数组归并到第三个数组中: 先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间: 五.代码 /** * 归并排序 * * @author

  • 实现Dijkstra算法最短路径问题详解

    实现Dijkstra算法最短路径问题详解

    1.最短路径问题介绍 问题解释: 从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径 解决问题的算法: 迪杰斯特拉算法(Dijkstra算法) 弗洛伊德算法(Floyd算法) SPFA算法 这篇博客,我们就对Dijkstra算法来做一个详细的介绍 2.Dijkstra算法介绍 算法特点: 迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树.该算法常用于路由算法或者作为其他图算法的一个子模块. 算法的思路 Dijk

  • C++递归与分治算法原理示例详解

    C++递归与分治算法原理示例详解

    目录 1. 汉诺塔问题 2. 全排列问题 4. 归并排序 5. 快速排序 6. 棋盘覆盖问题 1. 汉诺塔问题 递归算法,分为 3 步:将 n 个 a 上的盘子借助 c 移动到 b ① 将 n-1 个 a 上的盘子借助 b 移动到 c ② 将 a 上的盘子移动到 b ③ 将 c 上的 n-1 个盘子借助 a 移动到 b 所有盘子都移动到 b 上了 void hanoi(int n,char a,char b,char c)//将n个碟子从a借助c 移到b { if(n==0) return; e

  • Python数据结构与算法之算法分析详解

    Python数据结构与算法之算法分析详解

    目录 0. 学习目标 1. 算法的设计要求 1.1 算法评价的标准 1.2 算法选择的原则 2. 算法效率分析 2.1 大O表示法 2.2 常见算法复杂度 2.3 复杂度对比 3. 算法的存储空间需求分析 4. Python内置数据结构性能分析 4.1 列表性能分析 4.2 字典性能分析 0. 学习目标 我们已经知道算法是具有有限步骤的过程,其最终的目的是为了解决问题,而根据我们的经验,同一个问题的解决方法通常并非唯一.这就产生一个有趣的问题:如何对比用于解决同一问题的不同算法?为了以合理的方式

  • C语言 数据结构与算法之字符串详解

    C语言 数据结构与算法之字符串详解

    目录 串的定义 串的比较 串的抽象数据类型 串的初始化 相关定义初始化 定长类初始化 串的堆式顺序存储结构(Heap) 初始化堆字符串 赋值操作 比较两个堆字符串的大小 串的定义 零个或多个字符组成的有限序列 串的比较 串的比较实际上是在比较串中字符的编码 存在某个k < min(n,m),使得ai = bi (i = 1,2,3,4..k) 如果 ak < bk  -->  那么srt1 < srt2 (反之也成立) 除去相等的字符,在第一个不相等的字符位置以Ascii码进行比较

  • Python中八大图像特效算法的示例详解

    Python中八大图像特效算法的示例详解

    目录 0写在前面 1毛玻璃特效 2浮雕特效 3油画特效 4马赛克特效 5素描特效 6怀旧特效 7流年特效 8卡通特效 0 写在前面 图像特效处理是基于图像像素数据特征,将原图像进行一定步骤的计算——例如像素作差.灰度变换.颜色通道融合等,从而达到期望的效果.图像特效处理是日常生活中应用非常广泛的一种计算机视觉应用,出现在各种美图软件中,这些精美滤镜背后的数学原理都是相通的,本文主要介绍八大基本图像特效算法,在这些算法基础上可以进行二次开发,生成更高级的滤镜. 本文采用面向对象设计,定义了一个图像

  • RC4加密关键变量及算法特点原理详解

    目录 什么是RC4 RC4算法特点 RC4加密的几个关键变量 RC4加密原理 什么是RC4 RC4加密算法是大名鼎鼎的RSA三人组中的头号人物Ron Rivest在1987年设计的密钥长度可变的流加密算法簇.RC4算法是一种在电子信息领域加密的技术手段,用于无线通信网络,是一种电子密码,只有经过授权的用户才能享受该服务. RC4 流密码是使用最广泛的流密码之一,它通过算法一次一个字节地加密消息,简单并且操作速度快. RC4是一种在电子信息领域加密的技术手段,用于无线通信网络,是一种电子密码,只有

  • Python基于纹理背景和聚类算法实现图像分割详解

    目录 一.基于纹理背景的图像分割 二.基于K-Means聚类算法的区域分割 三.总结 一.基于纹理背景的图像分割 该部分主要讲解基于图像纹理信息(颜色).边界信息(反差)和背景信息的图像分割算法.在OpenCV中,GrabCut算法能够有效地利用纹理信息和边界信息分割背景,提取图像目标物体.该算法是微软研究院基于图像分割和抠图的课题,它能有效地将目标图像分割提取,如图1所示[1]. GrabCut算法原型如下所示: mask, bgdModel, fgdModel = grabCut(img,

随机推荐