深入第K大数问题以及算法概要的详解
发布时间：2022-05-22 16:52:29
标签：大数算法
解法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
投稿猜你喜欢
1 前言一般我们在Android的APP开发中，APP的界面如下： 可以看到，有状态栏、ActionBar(ToolBar)、导航- 本文实例讲述了C# DataTable中Compute方法用法。分享给大家供大家参考，具体如下：Compute函数的参数就两个：Expres
- 浅谈java 执行jar包中的main方法通过 OneJar 或 Maven 打包后 jar 文件，用命令：java -jar ****.j
- java中多种方式读文件 一、多种方式读文件内容。 1、按字节读取文件内容 2、按字符读取文件内容 3、按行读取文件内容 4、随机读取文件内
- 有时，类或方法需要对类型变量加以约束。下面是一个典型的例子，我们要寻找数组中的最小元素：public class ArrayAlg { &n
- 添加jar包这里的Scala不是maven工程所以要找到项目结构（快捷键：同时按住Ctrl+shift+Alt+s）在模块里面添加添加MyS
- 定义JAVA反射机制是在运行状态中，对于任意一个类，都能够知道这个类的所有属性和方法；对于任意一个对象，都能够调用它的任意方法和属性；这种动
- 前言Java中容器对象主要用来存储其他对象，根据实现原理不同，主要有3类常用的容器对象：1、ArrayList 使用数组结构存储容器中的元素
- StringBuilder内部是由多段char[]组成的半自动链表，因此频繁从中间修改StringBuilder，会将原本连续的内存分隔为多
- 直接上代码，代码中使用四种方法遍历Hashtable。using System;using System.Collections;names
- 前言： 在命令行中输入可以输入各类参数，本文将针对这些参数做一个小结。基于命令行输入参数测试程序如下：import java.util.Ar
- 目录Spring是什么？Spring Boot是什么？Maven依赖项springboot为不同的Spring模块提供了许多启动程序依赖项。
- Android canvas drawBitmap方法详解及实例之前自己在自定义view，用到canvas.drawBitmap
- android读取assets文件下的内容，一般都是使用getAsset.open()方法，并将文件的路径作为参数传入，而当我们解析一个目录
- 本文实例为大家分享了java实现飞机游戏的具体代码，供大家参考，具体内容如下ＭyGameFrame类:主要的调用类package sc.wh
- 断言的概念断言用于证明和测试程序的假设，比如“这里的值大于 5”。断言可以在运行时从代码中完全删除，所以对代码的运行速度没有影响。断言的使用
- 最近做的一个小东西遇到这样的情况，我从一个页面MainActivity修改一些内容，需要跳转到一个新的EditActivity去做修改操作，
- 本文实例为大家分享了java读取excel文件的具体代码，供大家参考，具体内容如下方式一：借用package com.ij34.util;/
- SpringBoot2.x过后static下的静态资源无法访问package com.example.thymeleaf.commons;i
- 1、final修饰类被final修饰的类不能被继承，因此final类的成员方法也不能被覆写，被final关键字修饰的类没有子类，因此类的实现
