两种方式可以让python实现查找最小的k个数
|
输入n个整数，找出其中最小的K个数。例如输入2221181109，4,5,1,6,2,7,3,8这8个数字，网上110报警平台则最小的4个数字是1,2,3,4,。 解法1 使用partition函数可以知道，使用==O(N)==的时间复杂度就可以找出第K大的数字，并且左边的数字比这个数小，右边的数字比这个数字大。因此可以取k为4，然后输出前k个数字，如果需要排序的话再对结果进行排序 # -*- coding:utf-8 -*- class Solution: def PartitionOfK(self, numbers, start, end, k): if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end: return low, high = start, end key = numbers[low] while low < high: while low < high and numbers[high] >= key: high -= 1 numbers[low] = numbers[high] while low < high and numbers[low] <= key: low += 1 numbers[high] = numbers[low] numbers[low] = key if low < k: self.PartitionOfK(numbers, start + 1, end, k) elif low > k: self.PartitionOfK(numbers, start, end - 1, k) def GetLeastNumbers_Solution(self, tinput, k): # write code here if k <= 0 or tinput == [] or k > len(tinput): return [] self.PartitionOfK(tinput, 0, len(tinput) - 1, k) return sorted(tinput[0:k]) #测试： sol = Solution() listNum = [4,5,1,6,2,7,3,8] rel = sol.GetLeastNumbers_Solution(listNum, 4) print(rel) 运行时间：30ms 占用内存：5732k 解法2 解法1存在两个问题，一个是partition把数组的顺序改变了，第二是无法处理海量的数据，海量的数组全部导入到内存里面做partition显然是不合适的。因此可以找出结果中最大的数字，如果遍历的数字比这个数字小，则替换，否则不变，可以采用堆的形式来实现数据结构，达到O(logK)的复杂度，因此整体的时间复杂度为N*O(logK) # -*- coding:utf-8 -*- class Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here if tinput == [] or k <= 0 or k > len(tinput): return [] result = [] for num in tinput: if len(result) < k: result.append(num) else: if num < max(result): result[result.index(max(result))] = num return sorted(result) #测试： sol = Solution() listNum = [4,5,1,6,2,7,3,8] rel = sol.GetLeastNumbers_Solution(listNum, 4) print(rel) 运行结果同上 （编辑：焦作站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
