Python最小的k个数

本文阅读 2 分钟
首页 Python笔记 正文

两种方法。第一种方法是基于划分的方法,如果是查找第k个数字,第一次划分之后,划分的位置如果大于k,那么就在前面的子数组中进行继续划分,反之则在后面的子数组继续划分,时间复杂度O(n);第二种方法是可以适用于海量数据的方法,该方法基于二叉树或者堆来实现,首先把数组前k个数字构建一个最大堆,然后从第k+1个数字开始遍历数组,如果遍历到的元素小于堆顶的数字,那么久将换两个数字,重新构造堆,继续遍历,最后剩下的堆就是最小的k个数,时间复杂度O(nlog k)。

  1. '''
  2. 输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。
  3. '''
  4. class Solution:
  5. # O(n)的算法, 只有当我们可以修改输入的数组时可用
  6. # 基于Partition的方法
  7. def GetLeastNumbers_Solution(self, tinput, k):
  8. if tinput == None or len(tinput) < k or len(tinput) <= 0 or k <=0:
  9. return []
  10. n = len(tinput)
  11. start = 0
  12. end = n - 1
  13. index = self.Partition(tinput, n, start, end)
  14. while index != k-1:
  15. if index > k-1:
  16. end = index - 1
  17. index = self.Partition(tinput, n, start, end)
  18. else:
  19. start = index + 1
  20. index = self.Partition(tinput, n, start, end)
  21. output = tinput[:k]
  22. output.sort()
  23. return output
  24. def Partition(self, numbers, length, start, end):
  25. if numbers == None or length <= 0 or start < 0 or end >= length:
  26. return None
  27. if end == start:
  28. return end
  29. pivotvlue = numbers[start]
  30. leftmark = start + 1
  31. rightmark = end
  32. done = False
  33. while not done:
  34. while numbers[leftmark] <= pivotvlue and leftmark <= rightmark:
  35. leftmark += 1
  36. while numbers[rightmark] >= pivotvlue and rightmark >= leftmark:
  37. rightmark -= 1
  38. if leftmark > rightmark:
  39. done = True
  40. else:
  41. numbers[leftmark], numbers[rightmark] = numbers[rightmark], numbers[leftmark]
  42. numbers[rightmark], numbers[start] = numbers[start], numbers[rightmark]
  43. return rightmark
  44. # O(nlogk)的算法, 适合海量数据
  45. # 利用一个k容量的容器存放数组, 构造最大堆, 当下一个数据大于最大数, 跳过, 小于最大数, 则进入容器替换之前的最大数
  46. def GetLeastNumbers(self, tinput, k):
  47. import heapq
  48. if tinput == None or len(tinput) < k or len(tinput) <= 0 or k <= 0:
  49. return []
  50. output = []
  51. for number in tinput:
  52. if len(output) < k:
  53. output.append(number)
  54. else:
  55. # 构造最小堆, 不推荐
  56. # output = heapq.nsmallest(k, output)
  57. # if number >= output[-1]:
  58. # continue
  59. # else:
  60. # output[-1] = number
  61. # 构造最大堆, 推荐
  62. output = heapq.nlargest(k, output)
  63. if number >= output[0]:
  64. continue
  65. else:
  66. output[0] = number
  67. return output[::-1] # 最小堆用 return output
  68. tinput = [4,5,1,6,2,7,3,8]
  69. s = Solution()
  70. print(s.GetLeastNumbers_Solution(tinput, 4))
  71. print(s.GetLeastNumbers(tinput, 4))
  72. print(s.GetLeastNumbers(tinput, 5))
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python数组中出现次数超过一半的数字
« 上一篇 01-21
Python连续子数组的最大和
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18497 篇
  • 评论总数:
    53318 条
  • 标签总数:
    8873 个
  • 总浏览量:
    22674205 次
  • 最后更新:
    3月27日

最多点赞

随便看看

标签TAG