有时候会突然被问到一些算法题，也是面试经常被问的思路问题吧，毕竟是师兄们面试回来说的面试考题。在这一系列呢，打算把自己每次被问到的仔细思考过的一些题都总结下来。方便自己去温习吧，也给大家参考一下我的思路。
文章结构：（1）题目描述；（2）快排思路解法；（3）堆排思路解法；（4）其他解法思路待续。
一、题目描述：
找出一个整型数组中第k大的数，并输出其下标。其中数组中的数有重复，重复的数据位置全部输出。
二、快排思路解法：
/*
核心思想：利用快排思想，先假定从大到小排序，找枢纽，枢纽会把大小分开它的两边，当枢纽下标等于k时，
即分了k位在它左边或右边，也就是最大或最小的排到了它的左边或右边了。那么那个枢纽就是要找的第k位了
*/
public class SearchNumData {
/*
n为数组长度
k为要查找的第k大
*/
public static int findKth(int[] a, int n, int K) {
return findKth(a, 0, n - 1, K);
}
/*
start为数组最低位下标
end为数组最高位下标
*/
public static int findKth(int[] a, int start, int end, int k) {
//先进行一次快排，取得枢纽
int pivot = partation(a, start, end);
//pivot-start+1表示快排的前半段元素的个数（包括中轴）
//当查了一次后，就划分了两边，大的在左边，小的在右边
if (k == pivot - start + 1){
return a[pivot];
} else if (k > pivot - start + 1) {//说明第k大的元素在后半段，所以往后面查，start=pivot+1，k-（pivot-start+1）。为什么这样更新，想一下，我们虽然往后查，但查的还是整个数组的第k大，第一次快排枢纽的时候，已经把大的放右边了。
return findKth(a, pivot + 1, end, k - pivot + start - 1);
} else{//则第k大的元素在前半段，更新end=pivot-1
return findKth(a, start, pivot - 1, k);
}
}
//快排，找枢纽，从大到小排序
public static int partation(int[] a, int low, int high) {
int key = a[low];
while (low < high) {
while (low < high && a[high] <= key)
high--;
a[low] = a[high];
while (low < high && a[low] >= key)
low++;
a[high] = a[low];
}
a[low] = key;
return low;
}
public static void main(String[] args) {
int[] array = {
9, 1, 5, 3, 5, 2, 6, 8, 7, 6
};//因为第一个数组被排序过了的，不是原来的了
int [] array2 = array.clone();//所以我clone一份原来的数组
int k=findKth(array,array.length,4);
System.out.print(k);
System.out.print("\n");
for(int i=0;i<10;i++){
System.out.print(array[i]+" ");
}
System.out.print("\n");
for(int i=0;i<10;i++){
if (k==array2[i]){
System.out.print(" 位置"+i+" ");
}
}
}
}
打印如下：
6
9 7 8 6 5 2 6 3 5 1
位置6 位置9
三、堆排思路解法：
/*
核心思路：有大根堆与小根堆两种
小根堆思路：构建一个k大小的小根堆，把数组的数全部装进去，边装边比较，大的始终会被丢到下面，而最小的会被放到堆顶！！所以装完之后，我们就可以确保，第k大的在小根堆堆顶。
大根堆思路：构建一个k大小的大根堆，把数组的数全部装进去，边装边比较，小的始终会被丢到下面，而每次放数的时候，都会调整把大数丢到最上面。所以装完之后，我们就可以确保，第k大的在大根堆堆顶了。
*/
public class HeapSearchNumData {
public static int findLeast(int[] nums, int k) {
PriorityQueue<Integer> q = new PriorityQueue<Integer>(k);//一个基于优先级堆的极大优先级队列
for (int i : nums) {
q.offer(i);//把数丢进堆里自动调整
if (q.size() > k) {
q.poll();//检索并移除此队列的头，也就是把堆顶的那个丢出去。
}
}
return q.peek();//单纯检查，不移除
}
public static void main(String[] args) {
int[] array = {
9, 1, 5, 3, 5, 2, 6, 8, 7, 6
};//这里就没有用clone来复制一份数组了，因为PriorityQueue有暂存空间。
int k=findLeast(array,4);
System.out.print(k);
System.out.print("\n");
for(int i=0;i<10;i++){
System.out.print(array[i]+" ");
}
System.out.print("\n");
for(int i=0;i<10;i++){
if (k==array [i]){
System.out.print(" 位置"+i+" ");
}
}
}
}
打印如下：
6
9 1 5 3 5 2 6 8 7 6
位置6 位置9
大家是不是看到了一个Java类PriorityQueue
一个基于优先级堆的极大优先级队列。此队列按照在构造时所指定的顺序对元素排序，既可以根据元素的自然顺序来指定排序（参阅 Comparable），也可以根据 Comparator 来指定，这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象。
默认：此队列的头是按指定排序方式的最小元素。
查询操作： poll、remove、peek 和 element 访问处于队列头的元素。
插入操作：此实现为插入方法（offer 和 add 方法）
删除：remove，poll
一个demo基本解出此类用法：更详细的文档
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue(3);
int[] array = {
9, 1, 5, 3, 5, 2, 6, 8, 7, 6
};
for (int i = 0; i < array.length; i++) {
pq.offer(array[i]);
System.out.print("\n");
Object[] a =pq.toArray();
for (int j =0;j<a.length;j++){
System.out.print(a[j]);
}
}
}
}
打印如下：
9
19
195
1359
13595
132955
1329556
13285569
132755698
1327556986
四、其他解法思路待续：
（1）耿直的排序，直接取值法：
public static int findNum(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
（2）利用哈希：
建立一个二维索引表，一维记录数组内容，另一维记录下标，对内容进行排序。元素有重复，但下标不会有重复。取到那个k内容，就是根据哈希取下标了。
好了，算法题（一）--找出数组中第k大的数并输出其下标（数组中的数有重复）讲完了。本博客系列是我学习过程中，被人问到的面试题（虽然大二的我还没到面试阶段，但既然被问到了，就做下咯，这些解法思路还是很开拓视野的），每遇一题我都会认真思考，列出多项解决之道给大家，分享经验给大家。欢迎在下面指出错误，共同学习！！你的点赞是对我最好的支持！！
网友评论