面试中会经常遇到手撕代码的情况,而求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次就好,不需要全部交换一遍。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持小牛知识库。
我创建了一个类,该类旨在获取2个分数,每个分数都有一个分子和分母,然后将它们相加,输出另一个分数。 当我编译程序时,我遇到了一个问题,涉及: 分数F3=新分数。添加(F1、F2);在主要方法中 错误:找不到类型分数$add 如果我将所有内容都设置为一个类,那么程序将运行,但我希望所有方法都严格位于Fraction类中,并在UseFraction类中调用Fraction。
我正在设计一个使用WordPress的网站,我在本地托管它与MAMP(Mac)。昨天我使用5.1版本的MAMP,今天我已经实现了它的5.2。 我将图像文件保存在wp content/themes/(mythmename)/images/中,以便以后在WordPress仪表板中编辑html时使用它们。但是它不再发现新的图像文件(在MAMP实现之后)。 我可以看到,在实现之后,我在应用程序中有两个MA
本文向大家介绍Python实现约瑟夫环问题的方法,包括了Python实现约瑟夫环问题的方法的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Python实现约瑟夫环问题的方法。分享给大家供大家参考,具体如下: 题目:0,1,...,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 定义函数f(n,m),表示每次在n个数字(0,1,.
用java实现以下场景,有100条商品,每个商品的价格0到1000元不等 商品数据: 例如200元 加价之后就是240元 利润是40元 首先把0到300元的商品的加价30%,301到500的加价20%,501到1000元商品的加价10%, 然后0到300元的商品订单有300条,301-500的商品订单有400条,501-1000的商品订单有300条, 最后计算他的总利润有多少,最好写出算法
2)Java的内置使用了两个锁:takeLock和putLock,并分别用在put()和take()中,我看到间隔队列是一个链表,不是线程安全的,那怎么行呢?
本文向大家介绍php实现约瑟夫问题的方法小结,包括了php实现约瑟夫问题的方法小结的使用技巧和注意事项,需要的朋友参考一下 本文实例总结了php实现约瑟夫问题的方法。分享给大家供大家参考。具体分析如下: 一群猴子排成一圈,按1,2,...,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数, 再数到第m只,在把它踢出去...,如此不停的进行下去, 直到最后只剩下一只猴子为止,