rt，首先自己思考了一下。维护一个n的大项堆，然后输出第k个根节点。当然也是自己很简单的一个思路（可能是因为最近比较爱堆排序吧）其实堆排序是比较适合文件量级很大的情况下，这样的效率比较快。比如后面文章提到的topk以及海量数据处理的面试。
（当然也需要记得做一些异常处理！比如说k>N的情况）
那么上网百度了一下。网上也给出了不同的答案。
1. 快速排序：从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
1）. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2）. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)；
这样也需要思考一下，数列本就是无序的情况，快排的每一次分区可以判断第k大的数在分区的哪个位置
2. 建立堆排序，pop出第k个数
3. 用Merge Sort算法，整个算法复杂度为 O(NlgN), 然后找到第K个即可
4. select算法
rt，首先自己思考了一下。维护一个n的大项堆，然后输出第k个根节点。当然也是自己很简单的一个思路（可能是因为最近比...
题目： 编写一段程序来查找第 n 个超级丑数。超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中...
一、题目 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes...
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整...
直接抄星主的： 编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 pri...
题目：在数组中找到第k大的元素（JAVA） 审题：输入：目标数n 输出：数组int[] nums 分析：...
题目：小易非常喜欢拥有以下性质的数列:1、数列的长度为n2、数列中的每个数都在1到k之间(包括1和k)3、对于位置...
题意：给n个数字表示一个长度为n的数组a，再给出一个长度为n的数组k，k[i] 表示数组a的a[k[i]] 在第i...
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。 示例： 提示： 1 <= k <...
题目：小易有一个长度为N的正整数数列A={A[1],A[2]..,A[N]},对数列A进行重新排列，使数列A满足所...
本文标题：如何在长度为n的数列中找到第k大的数
本文链接：https://www.haomeiwen.com/subject/digphxtx.html
网友评论