题解 | #最小的K个数#

NC119 最小的K个数

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

数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000

要求：空间复杂度 O(n) ，时间复杂度 O(nlogn)

思路：这题挺简单的，就是定义一个数组result存放要返回的结果，result升序排列。从input中取出一个数i，如果 i >= result[k-1]，就不操作。如果 i < result[k-1]就把i存放到result中，用二分的方式存入，存入后若len(result)比k大，则删除最后一个元素。

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    @staticmethod
    def insertArr(result,i):
        if len(result) == 0:
            result.append(i)
            return result
        left = 0
        right = len(result) - 1
        middle = (left + right) >> 1
        while left < right:
            middle = (left + right) >> 1
            if result[middle] == i:
                result.insert(middle,i)
                return result
            elif result[middle] < i:
                if result[middle + 1] > i:
                    result.insert(middle + 1, i)
                    return result
                left = middle + 1
            else:
                if result[middle - 1] < i:
                    result.insert(middle, i)
                    return result
                right = middle - 1
        if result[left] < i:
            result.insert(left + 1, i)
        else:
            result.insert(left, i)
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        result = []
        if k == 0:
            return []
        for i in input:
            if len(result) < k:
                self.insertArr(result,i)
            elif i < result[k-1]:
                self.insertArr(result,i)
                result.pop()
        return result