嵌套循环bug - java
我正在尝试解决这个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;
}“假设你是一个很棒的家长，想给你的孩子一些饼干。但是，你应该给每个孩子最多一个饼干。每个孩子都有一个贪婪因子gi，这是孩子满意的最小饼干大小；每一个饼干j都有一个sj大小。如果sj >= gi，我们可以把cookie j分配给我，而孩子我会很满意。你的目标是最大化你的内容孩子的数量并输出最大数量。注意:你可能假设贪婪因素总是正面的。你不能给一个孩子分配一个以上的饼干。”
示例1：
投入: 1,2,3，1,1
产出:1
说明:你有3个孩子和2个饼干。3名儿童的贪婪因子为1，2，3。
即使你有两个饼干，因为它们的大小都是1，你只能让贪婪因素是1内容的孩子。你需要输出1。“
回答 4
Stack Overflow用户
发布于 2018-12-30 03:27:36
我在你的代码里发现了一些缺失的东西。
你在为一个孩子尝试所有的饼干。这是做的，直到一个曲奇满足孩子。虽然cookie标记为-1，但摊销时间很长，因为对-1的检查仍将再次进行。理想情况下，应该避免这种检查，因为cookie已经被使用了。
其次，如果数组没有排序，则可能与perfect cookie不匹配。这里的其他答案中也存在着理性。
将使用过的cookie标记为-1是一个聪明的举动，但这个问题并不是必需的。您的运行时是O(nm)，但是可以在O(n)中完成，方法是将排序好的数组迭代在一起，并保持读取子数组和最后使用cookie的指针。
不包括排序部分，计算时间复杂度。
Stack Overflow用户
发布于 2018-12-30 03:08:47
您正在查看cookies和子程序，以便它们出现，而不是排序顺序。如果您有cookies 1，2，3和子代3，2，1，那么只有当您有一个完美的匹配时，您才会匹配两个cookie。您需要对数组进行排序，或者使用像堆一样的数据结构，以便最大化cookie分发。
Stack Overflow用户
发布于 2018-12-30 03:10:29
对两个数组进行排序。
Arrays.sort(greed);
Arrays.sort(size);在上面引用的例子中，假设贪婪为4,5，大小为5,4。没有排序(根据您的逻辑)，只能满足一个子级，但通过排序，您可以满足这两个子级。
https://stackoverflow.com/questions/53974895
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号