刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：

输入：stock = [2,5,7,4], cnt = 1
输出：[2]

示例 2：

输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]

提示：

• 0 <= cnt <= stock.length <= 10000
• 0 <= stock[i] <= 10000

思路

首先声明下，这道是个简单题，开始做主要是单纯想手撕一把快排，但是看了题解才发现果然是学无止境，切莫固步自封。

这道题简单就简单在思路很清晰明了，一眼排序，无论是其他排序弄完直接截取返回，还是堆排只找出前几个，思路都很直接，没有弯弯绕。

但，优化还是有的

先贴优化思路链接：来自K神的题解

简单描述下就是

既然快排是在用一个基准划分为比基准大和比基准小两段数组
那么以升序数组为例，当基准位置恰好处于cnt时，前cnt个数组就是题解
基于此，可以让快排进入下一层排序时，从深入排序左右两段变为了选择性排序其中一段甚至无需再排

详细内容可以点击链接去LeetCode看下～

没其他要说的了，直接上代码，细节在注释~

代码

快排

func inventoryManagement(stock []int, cnt int) []int {
    // 所有内容都是需要返回的，无需排序了
    if cnt >= len(stock) {
        return stock
    }
    var quickSort func(l, r int)
    quickSort = func(l, r int) {
        // 快排退出条件
        if l >= r {
            return
        }
        i, j := l, r
        for i < j {
            // 以 stock[l] 为基准
            // 想要升序排序，需要先从后往前找
            // 反例就是基准数是最小值时
            // 不太理解可以自己推导试下，或者私信交流
            for i < j && stock[j] >= stock[l] {
                j--
            }
            // 再从前往后找
            for i < j && stock[i] <= stock[l] {
                i++
            }
            // 交换不符合升序的两个数
            stock[i], stock[j] = stock[j], stock[i]
        }
        // 这一轮找完了，把基准摆到它应该在的位置，继续深入快排
        stock[i], stock[l] = stock[l], stock[i]
        quickSort(l, i-1)
        quickSort(i+1, r)
    }
    quickSort(0, len(stock)-1)
    return stock[:cnt]
}

优化快排

func inventoryManagement(stock []int, cnt int) []int {
    // 所有内容都是需要返回的，无需排序了
    if cnt >= len(stock) {
        return stock
    }
    var quickSort func(l, r int)
    quickSort = func(l, r int) {
        // 前半部分正常进行快排的操作
        i, j := l, r
        for i < j {
            for i < j && stock[j] >= stock[l] {
                j--
            }
            for i < j && stock[i] <= stock[l] {
                i++
            }
            stock[i], stock[j] = stock[j], stock[i]
        }
        stock[i], stock[l] = stock[l], stock[i]
        
        // 退出条件修改，以升序快排为例，当前面的元素少于所需个数，往后半部分继续找
        if cnt > i {
            quickSort(i+1, r)
            return
        } else if cnt < i {
            // 当前面的元素大于所需个数，往前半部分继续找
            quickSort(l, i-1)
            return
        }
        // 恰好相等于所需个数，直接返回就好
        return
    }
    quickSort(0, len(stock)-1)
    return stock[:cnt]
}