描述

给定一个长度为 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)

示例

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

// 输入：
[1],0
// 返回值：
[]

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

解题思路

• 排序
• 取排序后数组前 4 位

代码实现

冒泡排序：

/**
 * 冒泡排序
 *
 * @param input int 整型一维数组
 * @param k int 整型
 * @return int 整型一维数组
 */
func getLeastNumbers(input []int, k int) []int {
    result := []int{}
    if k == 0 {
        return result
    }

    count := len(input)
    if count < k {
        return result
    }

    for i := 0; i < count; i++ {
        for j := 0; j < count-1; j++ {
            if input[j] > input[j+1] {
                input[j], input[j+1] = input[j+1], input[j]
            }
        }
    }
    result = input[:k]

    return result
}

快排：

func quickSort(arr []int, left int, right int) {
    if left > right {
        return
    }

    tmp := arr[left]
    i := left
    j := right

    for i != j {
        for arr[j] >= tmp && i < j {
            j--
        }
        for arr[i] <= tmp && i < j {
            i++
        }
        if i < j {
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[left], arr[i] = arr[i], arr[left]

    quickSort(arr, left, i-1)
    quickSort(arr, j+1, right)
}

/**
 * 快排
 *
 * @param input int 整型一维数组
 * @param k int 整型
 * @return int 整型一维数组
 */
func getLeastNumbers2(input []int, k int) []int {
    result := []int{}
    if k == 0 {
        return result
    }

    count := len(input)
    if count < k {
        return result
    }

    quickSort(input, 0, count-1)
    result = input[:k]

    return result
}