您好,登錄后才能下訂單哦!
本文實(shí)例講述了Python實(shí)現(xiàn)查找最小的k個(gè)數(shù)。分享給大家供大家參考,具體如下:
題目描述
輸入n個(gè)整數(shù),找出其中最小的K個(gè)數(shù)。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字,則最小的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)。
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)學(xué)運(yùn)算技巧總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。