最小的k个数-剑指offer40-python

本文主要是介绍最小的k个数-剑指offer40-python，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

算法思想

排序思想比较简单，时间复杂度是O(nlogn)，代码不展示了。

利用类似快排的思想，可以使时间复杂度为O(n)。

python

class Solution:
    
    def partition(self, arr, left, right):
        i = left - 1
        pviot = arr[right]
        for j in range(left, right):
            if arr[j] < pviot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        
        arr[i+1], arr[right] = arr[right], arr[i+1]
        
        return i+1
    
    def select(self, arr, left, right, k):
        
        i = self.partition(arr, left, right)
        num = i - left + 1
        if num < k:
            self.select(arr, i+1, right, k-num)
        elif num > k:
            self.select(arr, left, i-1, k)
            
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k == 0:
            return []
        self.select(tinput, 0, len(tinput)-1, k)
        
        return tinput[:k]

这篇关于最小的k个数-剑指offer40-python的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！