这两种方式可以教你让python实现查找最小的k个数

解法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)


欢迎咨询维新科技
当前有客服在线,点击即可咨询