剑指offer-python：37.求最小的k个数/最大的k个数_不去重的k个数的数组

最小的k个数：

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

输入：[4,5,1,6,2,7,3,8],4 
返回值：[1,2,3,4]
说明：返回最小的4个数即可，返回[1,3,2,4]也可以

思路：快排（递归，二分法，分两段）

首先快排：

class Solution:
    def func0(self , nums):
        if len(nums) == []:
            return None
        start , end = 0 , len(nums)-1
        self.func1(nums , start , end)
        return nums
 
    def func1(self,nums , start , end):
        l , r = start , end
        if l >= r:
            return nums
        target = nums[start]   # target设置为数组的第一个数，也就是作为二分的中间值m，左边<m，右边>m
        while l<r:
            while l<r and nums[r] > target: # 分两段，把右边小于target的交换到左边
                r -= 1
            nums[l] , nums[r] = nums[r] , nums[l]
            while l<r and nums[l] <= target:  # 把左边大于target的交换到右边
                l += 1
            nums[l] , nums[r] = nums[r] , nums[l]
        nums = self.func1(nums , start ,l-1 )
        nums = self.func1(nums, r+1 , end)
        return nums
 
a = [30,24,5,58,18,36,12,42,39,44]
s = Solution()
print(s.func0(a))

 本题求最大/最小的k个数，再加个索引即可。