如何解决Hackerrank的Mark and Toys题目测试用例失败问题

问题排查 #

你代码的错误主要出在两个地方：

1. 遍历计数逻辑错误 #

你的现有逻辑是先扣除当前玩具价格，再判断剩余预算是否小于当前玩具价格，这个判断逻辑完全不符合需求，且计数返回值少了1：
举题目给出的第一个示例验证：prices = [1,2,3,4]，k=7
你的代码执行过程：

• 扣除1后剩余6，判断6<1不成立，继续
• 扣除2后剩余4，判断4<2不成立，继续
• 扣除3后剩余1，判断1<3成立，返回l=2
  但此时你已经成功购买了3件玩具，正确返回值应为3，和实际结果差了1，属于逻辑错误。
  同时如果扣除当前玩具价格后剩余预算为负，说明当前玩具买不起，不应该计入购买数量。

2. 排序算法效率不足 #

你使用的冒泡排序时间复杂度为O(n²)，当测试用例的玩具数量规模达到1e4以上时，会直接触发超时，无法通过大数量级的测试用例。

修正后代码 #

import "sort"

func maximumToys(prices []int32, k int32) int32 {
    // 用标准库排序，时间复杂度O(nlogn)，效率更高
    sort.Slice(prices, func(i, j int) bool {
        return prices[i] < prices[j]
    })
    
    var count int32 = 0
    for _, price := range prices {
        if k >= price {
            k -= price
            count++
        } else {
            // 已经排序，后面的价格更高，直接跳出
            break
        }
    }
    return count
}

逻辑说明 #

1. 先对价格数组做升序排序，优先买便宜的才能拿到最大数量，这部分你的原始思路是对的
2. 遍历排序后的价格，先判断当前预算是否足够买当前玩具：
   • 足够就扣除对应金额，计数+1
   • 不够就直接跳出循环，后面的玩具价格更高，不需要再判断
3. 最后返回计数即可，覆盖所有边界情况：
   • 所有玩具都买得起，返回数组长度
   • 一件都买不起，返回0
   • 预算刚好花完，返回对应计数

内容的提问来源于stack exchange，提问作者Titanio Yudista