java - 嵌套循环错误 - java

Question

我正在尝试解决这个 leetcode 挑战，但它没有通过 3 项测试。我不明白我做错了什么。这是我的代码:

public int findContentChildren(int[] greed, int[] size) {

    if (size.length == 0 || greed.length == 0) return 0;

    int satisfied = 0;

    for (int i = 0; i < greed.length; i++) {
        for (int j = 0; j < size.length; j++) {
            if (greed[i] <= size[j]) {
                satisfied++;
                size[j] = -1;
                break;
            }
        }
    }
    return satisfied;
}

“假设你是一位很棒的 parent ，想给你的 child 一些 cookies 。但是，你最多应该给每个 child 一个 cookies 。每个 child i 都有一个贪婪因子 gi，这是 child 会满意的 cookie 的最小大小；每个 cookie j 都有一个大小 sj 。如果 sj >= gi，我们可以将 cookie j 分配给 child i， child i 就会感到满意。你的目标是最大化你的内容 child 的数量并输出最大数量。笔记:您可能会假设贪婪因素始终为正。您不能将多个 cookie 分配给一名 child 。

示例1:

输入:[1,2,3], [1,1]

输出:1

说明:您有 3 个 child 和 2 个 cookie。 3个 child 的贪婪因子分别是1、2、3。

即使你有 2 个 cookie，由于它们的大小都是 1，所以你只能让贪婪因子为 1 的 child 满足。您需要输出 1。”

https://leetcode.com/problems/assign-cookies/

Answer 1

我发现您的代码中缺少一些内容。

您正在为 child 尝试所有 cookie。这样做直到一 block cookies 让 child 满意为止。尽管 cookie 被标记为 -1，但摊销时间很高，因为仍会再次对 -1 进行检查。理想情况下，应该避免此检查，因为 cookie 已被使用。

其次，如果数组未排序，您可能无法匹配完美的cookie。原因已在此处的其他答案中找到。

将使用的 cookie 标记为 -1 是一个聪明的举动，但对于这个问题来说不是必需的。您的运行时间是 O(nm)，但可以通过将排序后的数组一起迭代并维护读取子项和上次使用的 cookie 的指针，在 O(n) 内完成。

时间复杂度的计算不包括排序部分。