Java实现TopK问题的方法
作者:早就戒了 发布时间:2023-11-10 20:32:14
标签: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;
// 此时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;// 标记换了哪一个位置
} 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 {
break;// 本身不需要再调整了
}
}
num[root_index] = rootValue;
}
}
算法核心思想:与一般的堆排序不同的是,TopK只需要堆尾与堆顶交换K次就好,不需要全部交换一遍。
来源:https://blog.csdn.net/qq_37169817/article/details/79893200
0
投稿
猜你喜欢
- 逆时针画圆弧,原理:将360度分割成36份,分别标出每10度角度时的坐标点,然后将每个点连接起来。 #include <io
- 工厂方法模式(Factory Method):定义一个用于创建对象的接口,让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其子类。工
- 前言虽然从学java的第一个程序——helloworld至今,已经有好几个年头了。当时自己找资料,看视频,学习了java的输入输出流,多线程
- 本文实例为大家分享了C# GDI+实现时钟表盘的具体代码,供大家参考,具体内容如下一、设计如下图界面按键“打开时钟&am
- 自定义 webflux 容器配置配置代码@Componentpublic class ContainerConfig extends Rea
- 前言目前Flutter三大主流状态管理框架分别是provider、flutter_bloc、getx,三大状态管理框架各有优劣,本篇文章将介
- 需求:有些时候,我们需要连接多个数据库,但是,在方法调用前并不知道到底是调用哪个。即同时保持多个数据库的连接,在方法中根据传入的参数来确定。
- 使用JAVA工程管理越来越多的jar包,担心导错了,多导了,漏导了怎么办?换一个IDE项目后项目会不会出一堆BUG,看的头皮发麻?自己写的代
- 我们通过学习Java基础知识,让自己正式踏入学习Java语言的行列,这篇博客是用来让我们真正的了解并应用面向对象的思想来实现的。使用简单的J
- 本文主要介绍我为桌面和 Web 设计的一个超级秘密 Flutter 项目使用了画布和可拖动节点界面。本教程将展示我如何使用堆栈来使用小部件完
- 本文实例讲述了C#实现对Json字符串处理方法,分享给大家供大家参考。具体分析如下:一般对于web应用开发人员来说对Json字符串都会很熟悉
- 前言java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也不能做出来非常好用,
- 方案一: 采用reflections 框架(此框架依赖com.google.guava)1、reflections框架地址:https://
- yaml语法注解配置文件两种形式application.properties和.yaml第一种语法 key=value第二种key:空格va
- 概述:Flutter中常用的滑动布局 ScrollView 有 SingleChildScrollView、NestedScrollView
- 传播inbound事件有关于inbound事件, 在概述中做过简单的介绍, 就是以自己为基准, 流向自己的事件, 比如最常见的channel
- Spring框架的关键组件是面向方面编程(AOP)框架。面向方面的编程不仅打破程序逻辑分成不同的部分称为所谓的担忧。跨越多个点的应用程序的功
- 背景:Spring Boot是由Pivotal团队提供的全新框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架使用了
- Struts2是流行和成熟的基于MVC设计模式的Web应用程序框架。 Struts2不只是Struts1下一个版本,它是一个完全重写的Str
- static修饰符是java里面非常常用的一个东西,用法也非常多。然而,在kotlin里竟然没有这个东西!那该如何替代呢?本文就总结了下ja