溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Python實現查找最小的k個數。分享給大家供大家參考，具體如下：
題目描述
輸入n個整數，找出其中最小的K個數。例如輸入4,5,1,6,2,7,3,8這8個數字，則最小的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)
運行結果同上
運行時間：25ms
占用內存：5724k
時間和空間占用都比解法1更優。
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數學運算技巧總結》、《Python數據結構與算法教程》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
