Jack Frost

算法题(一)–找出数组中第k大的数并输出其下标(数组中的数有重复)

有时候会突然被问到一些算法题,也是面试经常被问的思路问题吧,毕竟是师兄们面试回来说的面试考题。在这一系列呢,打算把自己每次被问到的仔细思考过的一些题都总结下来。方便自己去温习吧,也给大家参考一下我的思路。

文章结构:(1)题目描述;(2)快排思路解法;(3)堆排思路解法;(4)其他解法思路待续。


一、题目描述:

找出一个整型数组中第k大的数,并输出其下标。其中数组中的数有重复,重复的数据位置全部输出。

二、快排思路解法:

打印如下:

三、堆排思路解法:

打印如下:

大家是不是看到了一个Java类PriorityQueue

一个基于优先级堆的极大优先级队列。此队列按照在构造时所指定的顺序对元素排序,既可以根据元素的自然顺序来指定排序(参阅 Comparable),也可以根据 Comparator 来指定,这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象。

默认:此队列的头是按指定排序方式的最小元素。

查询操作: poll、remove、peek 和 element 访问处于队列头的元素。

插入操作:此实现为插入方法(offer 和 add 方法)

删除:remove,poll

一个demo基本解出此类用法:更详细的文档)

打印如下:


四、其他解法思路待续:

(1)耿直的排序,直接取值法:

(2)利用哈希:

建立一个二维索引表,一维记录数组内容,另一维记录下标,对内容进行排序。元素有重复,但下标不会有重复。取到那个k内容,就是根据哈希取下标了。


源码下载:辅助的数据结构与算法系列(基础知识笔记跟题目会慢慢列出来)

好了,算法题(一)–找出数组中第k大的数并输出其下标(数组中的数有重复)讲完了。本博客系列是我学习过程中,被人问到的面试题(虽然大二的我还没到面试阶段,但既然被问到了,就做下咯,这些解法思路还是很开拓视野的),每遇一题我都会认真思考,列出多项解决之道给大家,分享经验给大家。欢迎在下面指出错误,共同学习!!你的点赞是对我最好的支持!!

更多内容,可以访问JackFrost的博客

码字很辛苦,转载请注明来自JackFrost《算法题(一)–找出数组中第k大的数并输出其下标(数组中的数有重复)》

Leave a Reply

Your email address will not be published. Required fields are marked *