文章/答案/技术大牛

发布

社区首页 >问答首页 >从未排序数组的中值中寻找K个最近的元素

问从未排序数组的中值中寻找K个最近的元素
EN

Stack Overflow用户

提问于 2017-11-12 12:24:45

回答 1查看 1.6K关注 0票数 2

给定一个未排序的数组，我试图找到与数组中值最近的K个元素。我很难在线性运行时间内找到解决方案。

A[] = 1, 2, 3, 4, 5 ,6 , 30 ,31, 32 ,33 ,34    # assume sorting part is done

中间值是6。

答案是2,3,4,5,6。

任何帮助或暗示都将不胜感激。

algorithm

sorting

回答 1

Stack Overflow用户

回答已采纳

发布于 2017-11-13 02:01:36

我对此的建议是分两步进行。

首先，使用中间值算法在线性时间内求出未排序阵列的中值。

其次，扫描数组并填充(大小为k)的最大堆，其中元素按照与中位数的距离排列，以便找到k个最近的元素。

您可以确保堆以下列方式永远不包含超过k个元素。当您想要将(k+1)th元素添加到堆中时，可以检查它是否小于根元素。如果是这样，则将其添加到堆中，并在堆重组后移除(新的)根。如果没有，你可以放弃它。

上面的运行时应该是O(N log(k))，在N中是线性的。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/47253561

复制

算法--排序--寻找数组内第K大的元素

编程算法

此题目，需要用到快速排序里的划分数组操作：快排参考：https://blog.csdn.net/qq_21201267/article/details/81516569#t2

Michael阿明

2021/02/20

5680

快排解决寻找数组中的第K个最大元素

算法

这是一个来自 leetcode 的题目，有很多的解决方式，属于排序类的问题。排序类的算法大致就这些几种排序算法，可以解决这个问题的比如冒泡排序、堆排序、快排等。最近有参与了几场面试，快排的伪代码也大概写了 3 次了，这次决定要使用快排解决这个问题。

_春华秋实

2020/07/21

9460

LeetCode 215. 数组中的第K个最大元素（快速排序）

编程算法

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

Michael阿明

2020/07/13

8080

数组中的第K个最大元素

编程算法

在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

WindRunnerMax

2020/08/27

1.2K0

寻找数组中第二小的元素

编程算法

方法一：用选择排序，冒泡法，或者交换排序这类的排序先把数组进行升序排序排完序后再进行遍历比较。排序算法中效率最高的时间复杂度为O(nlnogn) public static void main(String[] args) { int arr[]={-4,-4,56,34,76,34,23,4,75,87,50,3,5,6,}; //冒泡排序 for(int i=0;i<(arr.length)-1;i++){ for(int

一觉睡到小时候

2019/07/03

2.8K0

干货 | 漫画：寻找无序数组的第k大元素

编程算法

————— 第二天 ————— 题目是什么意思呢？比如给定的无序数组如下：如果 k=6，也就是要寻找第6大的元素，这个元素是哪一个呢？显然，数组中第一大的元素是24，第二大的元素是20，第三大的元素是17 ...... 第6大的元素是9。方法一：排序法这是最容易想到的方法，先把无序数组从大到小进行排序，排序后的第k个元素，自然就是数组中的第k大元素。方法二：插入法维护一个长度为k的数组A的有序数组，用于存储已知的k个较大的元素。接下来遍

腾讯NEXT学位

2019/12/03

5700

LeetCode，数组中的第K个最大元素

编程算法

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

微客鸟窝

2021/08/18

9270

leetcode:数组中的第K个最大元素

leetcode 队列排序数组优化

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

利刃大大

2023/04/12

5380

[随缘一题]排序数组中的单个元素

编程算法

因为我发现每日一题太难了,,,总会出现一些加班已经很累了(懒得不想动)的时候,而且周末有事多做两道题都叫做同一天的每日一题也让我这个强迫症贼难受.

呼延十

2019/07/01

2.2K0

215. 数组中的第K个最大元素

大数据

维护一个小根堆,把元素添进去,只要堆大小超过了k值,我们就进行出堆,这样留在最后的就是k个最大数据,其中堆顶就是目前k个最大数据的最小值即我们求的数组中第 k 个最大的元素。

名字是乱打的

2021/12/24

4230

215. 数组中的第K个最大元素

排序数组

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

张伦聪zhangluncong

2022/10/26

5250

Go寻找数组中最小的k个数——全部排序和部分排序

编程算法

今天分享的是数组中寻找k个最小数的解题思路，分别是全部排序和部分排序，一起来看看吧~

陌无崖

2020/07/27

1.2K0

三刷”数组中的第K个最大元素“，我终于学会了堆排序

二叉树编程算法

持续创作，加速成长！这是我参与「掘金日新计划 · 6 月更文挑战」的第19天，点击查看活动详情

虎妞先生

2022/10/27

4400

寻找旋转排序数组中的最小值

数据结构编程算法

题意假设一个旋转排序的数组其起始位置是未知的（比如 0 1 2 4 5 6 7 可能变成是 4 5 6 7 0 1 2）。你需要找到其中最小的元素。你可以假设数组中不存在重复的元素。样例给出 [4,5,6,7,0,1,2] 返回 0。代码实现：顺序查找 public class Solution { /** * @param nums: a rotated sorted array * @return: the minimum number in the arra

一份执着✘

2018/06/04

1.6K0

LeetCode34|数组中的第k个最大元素

java 编程算法

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

码农王同学

2020/08/25

5270

leetcode-215. 数组中的第K个最大元素

java leetcode 队列数组

这道题可以用优先队列建立小根堆，将所有数加入到小根堆中，并限制小根堆的个数为 k，因此最大的数在最下边，第 k 大的数就是堆顶的数，返回堆顶的数即可。

灰太狼学Java

2022/06/17

4090

LeetCode-215-数组中的第K个最大元素

java 编程算法

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

benym

2022/07/14

3570

漫画：寻找无序数组的第k大元素（修订版）

编程算法

1.方法二中，插入数组A的条件是遍历到的元素“大于”数组A的最小元素，而非”小于”。

小灰

2022/07/05

2910

快排查找数组中的第K个最大元素

编程算法

两种时间复杂度为O(nlogn)的排序算法，归并排序和快速排序。这两种排序算法适合大规模数据排序，更常用。

JavaEdge

2021/12/07

4.1K0

代码优化 - 求数组中的第 K 个最大元素

sort 排序性能优化

题目要求：解法一：直接用 sort 从大到小排序，取第 k 个 var findKthLargest = function (nums, k) { nums.sort((a, b) =

Leophen

2019/11/13

6150

相似问题

为数组中的每个元素寻找k个最近的整数

使用quickselect查找离中值最近的第k个元素

寻找K个最近点的并行算法

与未排序数组最近的k

217

使用“分治”和“中值”从未排序的数组中查找缺少的数字

213

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问从未排序数组的中值中寻找K个最近的元素
EN