首页 > 试题广场 >

查找第K大的元素

[编程题]查找第K大的元素
  • 热度指数：11269 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个无序的整型数组A[n],数组大小大于等于3,允许有值相同的元素;请设计算法找到该数组排序后第三大的元素值并输出.

输入描述:
一个非空的整数数组(至少有3个元素,可正可负)


输出描述:
第三大的元素值
示例1

输入

[1,2,3,4,5]

输出

3
示例2

输入

[1,1,2,2,3]

输出

2
示例3

输入

[6,5,4,4,1,2]

输出

4
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-05 15:48:23
精华题解 题解 该问题为排序问题，给出几种常用方法： 方法（一） 使用vector，用库函数sort进行排序。 #include<vector> #include<iostream> #include<algorithm> using namespace std; bool 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 白色高跟鞋
发表于 2020-06-20 17:01:29
其实不一定需要排序，采用类似快排的想法，随机挑选划分成三堆：比P小的、P、大等于P的。然后判断P在当前子序列中的位置距离，其右侧有几个比它大的: k-1个比它大的，返回P即可； 比k-1个少，在左侧序列中到k-1-offset个即可。offset是当前比P大的个数。 比k-1个多，迭代右侧序列。 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 shopee内推虾
发表于 2020-04-16 22:26:34
想到第k大元素, 很明显就是topk问题第k大就是要利用堆的特性 思路 维护一个k大小的最小堆, 然后把剩下的元素依次与堆顶进行比较, 如果大于堆顶就舍弃堆顶元素把更大的元素作为新堆顶, 然后向下调整维护堆的性质时间复制度, 建堆 (k/2)log(k) , 维护第k大, (n-k)log(k), 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客245611291号
发表于 2020-05-28 00:16:13
topk问题问题 方法1 -- 利用小根堆 维护一个k大小的最小堆（每次出堆的元素是堆中最小的元素）, 然后把剩下的元素依次与堆顶进行比较, 如果大于堆顶就舍弃堆顶元素把更大的元素作为新堆顶, 然后继续维护小根堆。 时间复杂度O(n*logk) 空间复杂度O(k) import java.uti 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客167622957号
发表于 2022-08-14 13:42:29
import json arr = input() arr = json.loads(arr) for i in range(len(arr) -1):     for& 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数组 2019 堆 有赞 查找 排序 Java工程师
上传者：小小
难度：
65条回答 15231浏览

热门推荐

通过挑战的用户

查看代码

相关试题

查找第K大的元素

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号