深入第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
投稿
猜你喜欢
- 常见Bean后处理器的作用:public static void main(String[] args) { &
- 使用背景项目中用户频繁访问数据库会导致程序的卡顿,甚至堵塞。使用缓存可以有效的降低用户访问数据库的频次,有效的减少并发的压力。保护后端真实的
- 本文实例讲述了Android开发获取重力加速度和磁场强度的方法。分享给大家供大家参考,具体如下:Android获取重力加速度和磁场强度主要依
- C#限速下载网络文件的方法,具体如下:using System;using System.Collections.Concurrent;us
- 前言最近,在给项目组使用Spring搭建Java项目基础框架时,发现使用Spring提供的BeanPostProcessor可以很简单方便地
- 问题描述这里我想测试某个与springboot相关的问题,结果在搭建mybatis时,发现没有成功从数据库中获取数据,报错信息为com.my
- 本文实例讲述了Winform下实现图片切换特效的方法,是应用程序开发中非常实用的一个功能。分享给大家供大家参考之用。具体方法如下:本实例源自
- 需求假设要设计一个名为estimate()的函数,估算编写指定行数的代码所需的时间,并且希望不同的程序员都可以使用该函数。对于所有的用户来说
- 位运算 位运算的运算分量只能是整型或字符型数据,位运算把运算对象看作是由二进位组成的位串信息,按位完成指
- 今天传图片,用的base64字符串,POST方法,前端传送的时候总是莫名其妙的崩溃,去网上搜了半天,以为是文件大小被限制了,但是我这个是字符
- 服务端注册功能实现通过web层完成客户端和服务端的数据交互(接受数据,发送数据),service层完成业务逻辑(注册,登录),dao层操作数
- 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其结构。这种类型的设计模式属于结构型模式,它是
- 本文实例讲述了C#读取csv格式文件的方法。分享给大家供大家参考。具体实现方法如下:一、CSV文件规则 1 开头是不留空,以行为单
- 目录首先必须要有一个个人微信公众号效果图后台路由代码完整代码首先必须要有一个个人微信公众号个人微信公众号相关的接口权限有限,不过用于个人学习
- 合并有序数组的实现java版本:实例代码public class Merge {//合并有序数组 public static v
- 修改readme.txt文件如下:Git is a distributed version control system.Git is fr
- Java 异步实现的几种方式1. jdk1.8之前的Futurejdk并发包里的Future代表了未来的某个结果,当我们向线程池中提交任务的
- Java内部类(Inner Class),类似的概念在C++里也有,那就是嵌套类(Nested Class),乍看上去内部类似乎有些多余,它
- 前言昨夜同门云集推杯又换盏,今朝茶凉酒寒豪言成笑谈。半生累,尽徒然,碑文完美有谁看,隐居山水之间誓与浮名散。简介今天给大家带来的是支付宝的月
- 1. 概述官方JavaDocsApi: java.awt.Component,java.awt.Containernull,绝对布局。绝对布