算法题练习——JS Node+python题解NC88 寻找第K大、NC119 最小的K个数

男娘i 2024-04-08 13:47 61阅读 0赞

**目录**

NC88 寻找第K大

NC119 最小的K个数

--------------------

### NC88 寻找第K大 ###

**描述**

> 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
> 
> 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

> 要求：时间复杂度 O(nlogn)，空间复杂度 O(1)
> 
> 数据范围：0≤n≤10^5，1≤K≤n，数组中每个元素满足0≤val≤10^9

**示例1**

> 输入：\[1,3,5,2,2\],5,3
> 
> 返回值：2

**示例2**

> 输入：\[10,10,9,9,8,7,5,6,4,3,4,2\],12,3
> 
> 返回值：9
> 
> 说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9

**JavaScript题解：**

/**
     * 
     * @param a int整型一维数组 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    function findKth( a ,  n ,  K ) {
        // write code here
        a.sort(function(a,b){return b-a})
        return a[K-1]
    }
    module.exports = {
        findKth : findKth
    };

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param a int整型一维数组 
    # @param n int整型 
    # @param K int整型 
    # @return int整型
    #
    class Solution:
        def findKth(self , a: List[int], n: int, K: int) -> int:
            # write code here
            a.sort(reverse=True)
            return a[K-1]

--------------------

### 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)

**示例1**

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

**示例2**

> 输入：\[1\],0
> 
> 返回值：\[\]

**示例3**

> 输入：\[0,1,2,1,2\],3
> 
> 返回值：\[0,1,1\]

**JavaScript Node题解：**

function GetLeastNumbers_Solution(input, k)
    {
        // write code here
        input.sort(function(a,b){return a-b})
        num = []
        while(k){
            num.push(input.shift())
            k--
        }
        return num
    }
    module.exports = {
        GetLeastNumbers_Solution : GetLeastNumbers_Solution
    };

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param input int整型一维数组 
    # @param k int整型 
    # @return int整型一维数组
    #
    class Solution:
        def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
            # write code here
            temp = sorted(input)
            num = list(temp)
            return num[:k]