Java实现TopK问题的方法

Java实现TopK问题的方法

面试中会经常遇到手撕代码的情况，而求TopK的是经常遇到的题目。下面我就用java来实现。主要通过两种方法实现，快排思想以及堆排序的思想，两者的复杂度为O（NlogK）。

基于快排的TopK实现：

import java.util.Arrays;

/**

* 使用快排实现的TopK问题 Title: Description: Company:

*

* @author 郑伟

* @date 2018年4月10日下午9:28:15

*/

public class TopK_PartitionSort {

public static void main(String[] args) {

int[] num = { 2, 20, 3, 7, 9, 1, 17, 18, 0, 4 };

partitionSort(num, 0, num.length - 1, 3);

System.out.println(Arrays.toString(num));

}

public static void partitionSort(int[] nums, int low, int high, int K) {

if (low < high) {

int pointKey = partitionSortCore(nums, low, high);

if (K - 1 == pointKey)//TopK问题的核心，就是如果返回的下标为K-1，说明已经排序好了K个最大/最小的数，但是之间的顺序是不确定的

return;

partitionSort(nums, low, pointKey - 1, K);

partitionSort(nums, pointKey + 1, high, K);

}

}

/**

* 快排的核心

*

* @param nums

* @param low

* @param high

* @return 返回排序好以后的位置

*/

public static int partitionSortCore(int[] nums, int low, int high) {

// 以第一个座位标志位来比对

int pivotkey = nums[low];

while (low < high) {

// 从pivotkey往最后一个位置比较

while (low < high && pivotkey <= nums[high]) {

--high;

}

// 开始交换pivotkey和nums[high]

int temp = nums[low];

nums[low] = nums[high];

nums[high] = temp;

kEEOrQ // 此时nums[high]对应于pivotkey

while (low < high && pivotkey >= nums[low]) {

++low;

}

// 找到比pivotkey大的书了，那就交换

temp = nums[low];

nums[low] = nums[high];

nums[high] = temp;

// 这时，pivotkey对应于nums[low]

}

return low;// 返回pivotkey对应的正确位置

}

}

其实整个代码和快排一样，就是多了一个下标位置的判断，if (K - 1 == pointKey)，这是核心，也就是为什么复杂度为NlogK。如果看不懂，可以先去理解快排的实现。

堆排序实现TopK：

/**

* 使用堆排序实现的TopK问题 Title: Description: Company:

*

* @author 郑伟

* @date 2018年4月11日上午9:28:15

*/

public class TopK_HeapSort {

public static void main(String[] args) {

int[] num = { 2, 20, 3, 7, 9, 1, 17, 18, 0, 4 };

heapSort(num,3);

System.out.println(Arrays.toString(num));

}

/**

* 堆排序

*

* @param num

*/

private static void heapSort(int[] num, int K) {

for (int i = num.length / 2 - 1; i >= 0; i--) {

adjustMin(num, i, num.length);// 调整0~num.length-1的数据

}

// 如果要实现topK，就在这里执行

for (int j = num.length - 1; j >= 0 && K > 0; j--,K--) {

// 交换最后一个

swap(num, 0, j);

// 再次调整0~j-1的数据

adjustMin(num, 0, j);

}

//使用最大堆，K=3，输出[9, 7, 3, 2, 4, 1, 0, 17, 18, 20]，最大的三个值17,18,20

//使用最小堆，K=3，输出[3, 4, 9, 7, 20, 18, 17, 2, 1, 0]，最小的三个值2,1,0

}

/**

* 交换栈顶和最后一个元素

*

* @param num

* @param i

* @param j

*/

private static void swap(int[] num, int i, int j) {

int tem = num[i];

num[i] = num[j];

num[j] = tem;

}

/**

* 调整为大顶堆

*

* @param num

* @param root_index

*/

private static void adjust(int[] num, int root_index, int length) {

//

int root = num[root_index];

for (int j = root_index * 2 + 1; j < length; j = j * 2 + 1) {

// 最大的儿子

if (j + 1 < length && num[j] < num[j + 1]) {

j = j + 1;// 指向了最大的儿子

}

if (root < num[j]) {

num[root_index] = num[j];

root_index = j;http://// 标记换了哪一个位置

} else {

break;// 已经是大顶堆了，不需要调整了

}

}

num[root_index] = root;

}

/**

* 小顶堆

*

* @param num

* @param root_index

* @param length

*/

private static void adjustMin(int[] num, int root_index, int length) {

//

int rootValue = num[root_index];

for (int k = root_index * 2 + 1; k < length; k = k * 2 + 1) {

if (k + 1 < length && num[k] > num[k + 1])

k = k + 1;// K指向最小的子节点

if (num[k] < rootValue) {

num[root_index] = num[k];

root_index = k;// 和k换了一下位置

} else {

brkEEOrQeak;// 本身不需要再调整了

}

}

num[root_index] = rootValue;

}

}

算法核心思想：与一般的堆排序不同的是，TopK只需要堆尾与堆顶交换K次就好，不需要全部交换一遍。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。