當前位置:首頁 >  站長 >  編程技術 >  正文

兩種方式可以讓python實現(xiàn)查找最小的k個數(shù)

 2020-11-25 10:47  來源: A5專欄   我來投稿 撤稿糾錯

  域名預訂/競價,好“米”不錯過

輸入n個整數(shù),找出其中最小的K個數(shù)。例如輸入2221181109,4,5,1,6,2,7,3,8這8個數(shù)字,網(wǎng)上110報警平臺則最小的4個數(shù)字是1,2,3,4,。

解法1

使用partition函數(shù)可以知道,使用==O(N)==的時間復雜度就可以找出第K大的數(shù)字,并且左邊的數(shù)字比這個數(shù)小,右邊的數(shù)字比這個數(shù)字大。因此可以取k為4,然后輸出前k個數(shù)字,如果需要排序的話再對結果進行排序

# -*- 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把數(shù)組的順序改變了,第二是無法處理海量的數(shù)據(jù),海量的數(shù)組全部導入到內存里面做partition顯然是不合適的。因此可以找出結果中最大的數(shù)字,如果遍歷的數(shù)字比這個數(shù)字小,則替換,否則不變,可以采用堆的形式來實現(xiàn)數(shù)據(jù)結構,達到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更優(yōu)

申請創(chuàng)業(yè)報道,分享創(chuàng)業(yè)好點子。點擊此處,共同探討創(chuàng)業(yè)新機遇!

相關文章

熱門排行

信息推薦