Top K 问题的最优解 |
您所在的位置：网站首页 › 快速指数算法图解 › Top K 问题的最优解 |
Top K 问题的最优解
|
文章目录
Leetcode 215. Kth Largest Element in an Array1.1：快速选择算法流程1.2：注意事项1.3：python实现
Leetcode 973. K Closest Points to Origin1.1 题意1.2 思路1.3 python实现
3. 牛客：最小的K个数3.1 题意：3.2 分析3.3 python实现
最后：heapq模块实现top N---nlargest()和nsmallest()函数
Leetcode 215. Kth Largest Element in an Array
题意：给定一个无序的数组，寻找第K大的元素。 1.1：快速选择算法流程输入： nums = [3,2,1,5,6,4] k=2 step 1： 随机选择一个 pivot，通过一系列计算，查看是否是我们需要找到的 Top k 对应的 pivot step 2: 把 pivot 移动到最右的位置，以最右为标杆，从头开始对剩余部分进行选择查找  step 3: 定义两个指针，初始化为0，查看 j 所在的指针是否小于等于 pivot，4 大于 3，所以我们把 j 指针右移一位  step 4: 查看 j 所在的指针是否小于等于 pivot，2 小于等于 3，我们替换 i 指针和 j 指针所在的位置，同时把 i 和 j 指针都右移一位。  step 5: 查看 j 所在的指针是否小于等于 pivot，1 小于等于 3，我们替换 i 指针和 j 指针所在的位置，同时把 i 和 j 指针都右移一位。  step 6: 重复上述步骤，直到 j 指针移动到最右边   step 7: 把pivot放到中间来，把数组划分为左右两个部分  step 8: 此时 pivot 3 左边的值都小于 3，右边的值都大于 3，pivot 3 对应的是 Top 4 而不是 我们需要找的 Top 2，但我们可以知道，Top 2 一定在 pivot 3 右边的位置。  step 9: 把右半部分按照重复执行上述步骤，最终找到 Top 2 的 pivot，对应的值为 5 
1.2：注意事项
pivot 的选择很重要，如果对于一个已排序的数组，我们每次都选择最大/最小的值为 pivot，那么时间复杂度为 O(N^2) 。每次通过 random 选择 pivot 可以尽量避免最坏情况发生。 快速选择算法的平均时间复杂度是 O(N)，但最坏情况下的时间复杂度是 O(N^2) ，因为我们已经随机选择 pivot，所以能够最大程度上的减少最坏情况发生 1.3：python实现 def findKthLargest(self, nums, k): def quickSelect(nums, lo, hi, k): # 从小到大排序 pivot = random.randint(lo, hi) # 0-len(nums)-1中随机取一个下标，避免最坏的情况 nums[hi], nums[pivot] = nums[pivot], nums[hi] # 最右边存这个支点 i = j = lo while j > import heapq >>> nums=[1,8,2,23,7,-4,18,23,42,37,2] >>> print(heapq.nlargest(3,nums)) # 从大到小排序 [42, 37, 23] >>> print(heapq.nsmallest(3,nums)) #从小到大排序 [-4, 1, 2] |
【本文地址】