LCR 159. 库存管理 III

LCR 159. 库存管理 III

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

---

被简单题难到了，相似，虽然以前没学过计数排序，但是这里我第一时间竟然不是想到的用排序做，哈哈。

计数排序

func inventoryManagement(stock []int, cnt int) []int {
    if cnt == 0 || len(stock) == 0 {
        return nil
    }
    var Cnt [100001]int
    for i := 0; i < len(stock); i ++ {
        Cnt[stock[i]] ++
    }

    ans := make([]int, cnt)
    idx := 0
    for i := range Cnt {
        for Cnt[i] > 0 && idx < cnt {
            Cnt[i] --
            ans[idx] = i
            idx ++
        }
    }
    return ans
}

---

快速选择

虽然，但是还是有很多地方有点难理解，但是自己认真写一遍，还是能够加深入理解的，开背吧）

func inventoryManagement(stock []int, cnt int) []int {
    rand.Seed(time.Now().UnixNano())
	randomizedSelected(stock, 0, len(stock)-1, cnt)
	return stock[:cnt]
}

func randomizedSelected(stock []int, l, r, k int) {
    if l >= r {
        return 
    }

    pos := randomized_partition(stock, l, r)
    num := pos - l + 1
    if k == num {
        return
    } else if k < num {
        randomizedSelected(stock, l, pos - 1, k)
    } else {
        randomizedSelected(stock, pos + 1, r, k - num)
    }
}

func randomized_partition(stock []int, l, r int) int {
    i := rand.Intn(r-l+1) + l
    stock[r], stock[i] = stock[i], stock[r]
    return partition(stock, l, r)
}

func partition(nums []int, l, r int) int {
    pivot := nums[r]
    i := l - 1
    for j := l; j <= r - 1; j ++ {
        if nums[j] <= pivot {
            i ++
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
    nums[i + 1], nums[r] = nums[r], nums[i + 1]
    return i + 1
}