輸入n個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)。例如輸入2221181109，4,5,1,6,2,7,3,8這8個(gè)數(shù)字，網(wǎng)上110報(bào)警平臺(tái)則最小的4個(gè)數(shù)字是1,2,3,4,。
解法1
使用partition函數(shù)可以知道，使用==O(N)==的時(shí)間復(fù)雜度就可以找出第K大的數(shù)字，并且左邊的數(shù)字比這個(gè)數(shù)小，右邊的數(shù)字比這個(gè)數(shù)字大。因此可以取k為4，然后輸出前k個(gè)數(shù)字，如果需要排序的話再對(duì)結(jié)果進(jìn)行排序
# -*- 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])
#測(cè)試：
sol = Solution()
listNum = [4,5,1,6,2,7,3,8]
rel = sol.GetLeastNumbers_Solution(listNum, 4)
print(rel)
運(yùn)行時(shí)間：30ms
占用內(nèi)存：5732k
解法2
解法1存在兩個(gè)問題，一個(gè)是partition把數(shù)組的順序改變了，第二是無法處理海量的數(shù)據(jù)，海量的數(shù)組全部導(dǎo)入到內(nèi)存里面做partition顯然是不合適的。因此可以找出結(jié)果中最大的數(shù)字，如果遍歷的數(shù)字比這個(gè)數(shù)字小，則替換，否則不變，可以采用堆的形式來實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)，達(dá)到O(logK)的復(fù)雜度，因此整體的時(shí)間復(fù)雜度為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)
#測(cè)試：
sol = Solution()
listNum = [4,5,1,6,2,7,3,8]
rel = sol.GetLeastNumbers_Solution(listNum, 4)
print(rel)
運(yùn)行結(jié)果同上
運(yùn)行時(shí)間：25ms
占用內(nèi)存：5724k
時(shí)間和空間占用都比解法1更優(yōu)
申請(qǐng)創(chuàng)業(yè)報(bào)道，分享創(chuàng)業(yè)好點(diǎn)子。點(diǎn)擊此處，共同探討創(chuàng)業(yè)新機(jī)遇！
