8.1分发饼干(LC455-E)
2024-01-07 21:23:42
算法:
局部最优:大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子,那么就应该优先满足胃口大的。局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个。
全局最优:喂饱尽可能多的小孩。
为什么局部最优能推出全局最优?
贪心算法没必要用数学方法去证明,如果想不出明显的反例,那就用贪心算法试试好了。
举个例子理解:
这个例子可以看出饼干 9 只有喂给胃口为 7 的小孩,这样才是整体最优解(输出3),并想不出反例,那么就可以撸代码了。
代码思路:
1.先把g和s排序
局部最优是大饼干喂给胃口大的,那怎么找出哪个大呢?所以要先排序!
2.要遍历胃口和饼干,那就要用for循环
注意顺序:先遍历胃口g(for循环),再遍历饼干s(在for循环里用if控制),若s[i] >= g[i],则满足一个输出,结果result++
可不可以 先遍历 饼干,再遍历胃口呢?
不可以。
试一下,如果 for 控制的是饼干, if 控制胃口,就会出现如下情况 :
if 里的 index 指向 胃口 10, for 里的 i 指向饼干 9,因为 饼干 9 满足不了 胃口 10,所以 i 持续向前移动,而 index 走不到s[index] >= g[i]
?的逻辑,所以 index 不会移动,那么当 i 持续向前移动,最后所有的饼干都匹配不上。
所以 一定要 for 控制 胃口,里面的 if 控制饼干。
调试过程:
第一次调试:
原因:
int result初始化没有赋值。
????????int result = 0;
int类型的length是属性,不用括号;而String的length是方法,需要括号
????????s.length
????????g.length
在 Java 中,数组并没有名为?`sorted
`?的方法。要对数组进行排序,可以使用?`Arrays.sort
`?方法。
????????Arrays.sort(g);
????????Arrays.sort(s);
第二次调试:
原因:
在写s[index] >= g[i]时,index不一定合法,比如s为空时,index=-1,为负值,无法作为索引
所以应改为:
if (index >=0 && s[index] >= g[i])
正确代码:
class Solution {
public int findContentChildren(int[] g, int[] s) {
//先排序,默认从小到大
Arrays.sort(g);
Arrays.sort(s);
int result = 0;
int index = s.length -1;
//for控制胃口g,if控制饼干s
for (int i =g.length-1; i >= 0; i-- ){
if (index >=0 && s[index] >= g[i]) {
result ++;
index--;
}
}
return result;
}
}
时间空间复杂度:
时间复杂度分析
- 排序数组?`
g
`?和?`s
`?的时间复杂度为O(nlog?n),其中?n?是数组的长度。 - 遍历数组?`
g
`?的时间复杂度为?O(n),其中?n?是数组的长度。 - 在最坏的情况下,我们需要遍历数组?`
g
`?一次,因此总体时间复杂度为O(nlog?n)。
空间复杂度分析
- 算法的空间复杂度为?O(1),因为它只使用了常数级别的额外空间来存储一些变量,与输入的规模无关。
文章来源:https://blog.csdn.net/m0_50696252/article/details/135431705
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!