算法题练习——NC45 实现二叉树先序，中序和后序遍历,NC119 最小的K个数

目录

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]