栈&队列&哈希表&堆-python  https://blog.csdn.net/qq_19446965/article/details/102982047

1、丑数 II

编写一个程序,找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:

1 是丑数。
n 不超过1690。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ugly-number-ii

先回忆一下《丑数 I》

编写一个程序判断给定的数是否为丑数。

https://leetcode-cn.com/problems/ugly-number-ii/

class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 0:
return False
if num == 1:
return True while num >= 2 and num % 2 == 0:
num /= 2
while num >= 3 and num % 3 == 0:
num /= 3
while num >= 5 and num % 5 == 0:
num /= 5 return num == 1

  

丑数 II有点相反

class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
import heapq
heap = [1]
visited = set([1]) num = None
for i in range(n):
num = heapq.heappop(heap)
for factor in [2, 3, 5]:
if num * factor not in visited:
visited.add(num * factor)
heapq.heappush(heap, num * factor) return num

 

2、Top k largest Number

例:n个数值选出最大k个数(3<k<n)的最小算法复杂度是( O(n) )

1.最简单的方法:将n个数排序,排序后的前k个数就是最大的k个数,这种算法的复杂度是O(nlogn)

2.O(n)的方法:

解法1:利用快排的patition思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况:

1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;

2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n),但最坏情况下复杂度为O(n^2)。

解法2:利用hash保存数组中元素Si出现的次数,利用计数排序的思想,线性从大到小扫描过程中,前面有k-1个数则为第k大数,平均情况下时间复杂度O(n)

3.O(nlogk)的方法:先创建一个大小为k的最小堆,接下来我们每次从输入的n个整数中读入一个数,如果这个数比最小堆的堆顶元素还要大,那么替换这个最小堆的堆顶并调整。

两种方法的优缺点:

堆排序适用于海量数据,即它不需要所有的数据都加载进内存,只需要维护一个大小为m的小顶堆,这是其一个巨大的优势。

快排方法速度快,但是面对海量数据是就显得无能为力了,因为他需要维护整个数组。

4..O(n)查找第K小的数 BFPRT算法 - warm3snow - 博客园  https://www.cnblogs.com/informatics/p/5092741.html

算法的思想是修改快速选择算法的主元选取方法,提高算法在最坏情况下的时间复杂度。其主要步骤为:

  1. 首先把数组按5个数为一组进行分组,最后不足5个的忽略。对每组数进行排序(如插入排序)求取其中位数。
  2. 把上一步的所有中位数移到数组的前面,对这些中位数递归调用BFPRT算法求得他们的中位数。
  3. 将上一步得到的中位数作为划分的主元进行整个数组的划分。
  4. 判断第k个数在划分结果的左边、右边还是恰好是划分结果本身,前两者递归处理,后者直接返回答案。

其预算法不作实现,本次只关注堆

class Solution:
def get_top_k(k, nums):
import heapq
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap) return sorted(heap, reverse=True)

3、合并k个排序链表

合并k个排序链表,并且返回合并后的排序链表。尝试分析和描述其复杂度。

class ListNode(object):

    def __init__(self, val, next=None):
self.val = val
self.next = next

方法一:归并算法

class Solution:
"""
@param lists: a list of ListNode
@return: The head of one sorted list.
"""
def mergeKLists(self, lists):
if not lists:
return None return self.merge_range_lists(lists, 0, len(lists) - 1) def merge_range_lists(self, lists, start, end):
if start == end:
return lists[start] mid = (start + end) // 2
left = self.merge_range_lists(lists, start, mid)
right = self.merge_range_lists(lists, mid + 1, end)
return self.merge_two_lists(left, right) def merge_two_lists(self, head1, head2):
tail = dummy = ListNode(0)
while head1 and head2:
if head1.val < head2.val:
tail.next = head1
head1 = head1.next
else:
tail.next = head2
head2 = head2.next
tail = tail.next if head1:
tail.next = head1
if head2:
tail.next = head2 return dummy.next

  

方法二:使用 heap

1、将所有元素加入到堆
2、遍历,一个一个取出最小值,连接起来
import heapq
ListNode.__lt__ = lambda x, y: (x.val < y.val) class Solution:
"""
@param lists: a list of ListNode
@return: The head of one sorted list.
"""
def mergeKLists(self, lists):
if not lists:
return None dummy = ListNode(0)
tail = dummy
heap = []
for head in lists: # 1、将所有元素加入到堆
if head:
heapq.heappush(heap, head) while heap: # 2、遍历,一个一个取出最小值,连接起来
head = heapq.heappop(heap)
tail.next = head
tail = head
if head.next:
heapq.heappush(heap, head.next) return dummy.next

  

———————————————————

参考:九章算法讲解 https://www.jiuzhang.com/solution/

最新文章

  1. The replication agent has not logged a progress message in 10 minutes.
  2. jquey on
  3. svn/git的diff、patch
  4. kafka 集群安装与安装测试
  5. iOS开发小技巧--利用苹果官方API播放视频(方法已经过时,了解一下)
  6. ASP.Net Core 运行在Linux(Ubuntu)
  7. 简单的javasrcipt选项卡
  8. Activity设置全屏显示的两种方式及系统自带theme属性解析
  9. 《Python编程从入门到实践》第三章_列表简介
  10. Oracle-1 - :超级适合初学者的入门级笔记,CRUD,事务,约束 ......
  11. 自己做一台3D打印机到底有多难?(附教程)
  12. Structured Streaming + Kafka 集成中遇到的问题
  13. 手把手教你从头开始搭建友善之臂ARM-tiny4412开发环境(史上最详细!!)
  14. (cvpr 2018)Technology details of SMRD
  15. 浏览器输入URL后,HTTP请求返回的完整过程
  16. [2017BUAA软工助教]团队建议
  17. python 全栈开发,Day33(tcp协议和udp协议,互联网协议与osi模型,socket概念,套接字(socket)初使用)
  18. Codeforces Round #319 (Div. 2) D - Invariance of Tree
  19. BZOJ.4653.[NOI2016]区间(线段树)
  20. 了解PHP中$_SERVER变量对路径的解析

热门文章

  1. [OpenCV实战]37 图像质量评价BRISQUE
  2. mybatis-config.xml 说明
  3. ArcGIS工具 - 统计工具数量
  4. Asp-Net-Webapi项目从Framework-4-5升级到-Net-6的总结
  5. AIGC 很火,想微调个自己的模型试试看?(不是卖课的)
  6. Linux简易入门
  7. 基于AS2协议的EDI 系统
  8. FLASH-CH32F103替换STM32F103 FLASH快速编程移植说明
  9. immutable.js学习笔记(四)----- OrederMap
  10. Linux存储服务