文章目录
- 题目
- 思路
- 代码实现
- 实现总结
- 主要步骤
- 时间复杂度
- 扩展问题
Hello，大家好，我是阿月。坚持刷题，老年痴呆追不上我，今天刷第一个贪心算法：分发饼干
题目
455.分发饼干
思路
要解决这个问题，可以使用贪心算法。具体步骤如下：
- 首先，对孩子们的胃口值 g[i] 和饼干的尺寸 s[j] 进行排序。
- 然后，从胃口值最小的孩子开始遍历，尝试满足他们的胃口。
- 对于每个孩子，找到能够满足其胃口的最小尺寸的饼干，尽可能地用小的饼干满足孩子，以便给其他孩子留下更大的饼干。
- 继续这个过程，直到所有的孩子都被满足或者没有足够的饼干。
代码实现
import java.util.Arrays;
public class CookieAndChildren {
public static int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int childIndex = 0;
int count = 0;
for (int i = 0; i < s.length && childIndex < g.length; i++) {
if (s[i] >= g[childIndex]) {
count++;
childIndex++;
}
}
return count;
}
public static void main(String[] args) {
int[] g = {1, 2, 3};
int[] s = {1, 1};
System.out.println(findContentChildren(g, s)); // 输出：1
int[] g2 = {1, 2};
int[] s2 = {1, 2, 3};
System.out.println(findContentChildren(g2, s2)); // 输出：2
}
}
实现总结
这个问题考察的是贪心算法的应用。贪心算法是一种在每一步选择中都采取当前状态下最优决策的策略，从而希望导致全局最优解。
在这个问题中，要尽可能地满足更多数量的孩子，因此采取了贪心策略：首先对孩子的胃口值和饼干的尺寸进行排序，然后从胃口值最小的孩子开始遍历，并尽可能用小的饼干满足他们的胃口。这样做的原因是，如果用一个大的饼干去满足一个小胃口的孩子，那么这个大饼干就可能无法满足更大胃口的孩子，导致最终满足的孩子数量较少。因此，选择尽可能小的饼干来满足胃口最小的孩子可以使得留下的饼干更有可能满足后面的孩子。
主要步骤
- 首先，对孩子的胃口值数组 g 和饼干的尺寸数组 s 进行排序，以便后续能够按照从小到大的顺序进行匹配。
- 使用两个变量
start和count分别表示当前要满足的孩子的索引和已满足孩子的数量。初始化start为 0，count为 0。 - 使用一个循环遍历饼干数组
s，并在循环中对比当前饼干的尺寸是否能够满足当前孩子的胃口。如果能够满足，则将count加一，并将start向后移动一位，表示已满足一个孩子。 - 最后返回满足孩子的数量
count。
这个实现利用了数组的排序，使得在遍历饼干数组时可以更有效地匹配满足孩子的胃口。同时，通过一次遍历，即可确定最终满足的孩子数量，具有较高的效率。
时间复杂度
这段代码的时间复杂度取决于两个排序操作和单次遍历操作。
- 对孩子的胃口值数组
g和饼干的尺寸数组s进行排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。 - 单次遍历操作的时间复杂度为 O(n)，其中 n 是较小的数组的长度（饼干数组或孩子数组）。
因此，总的时间复杂度为 O(n log n)，其中 n 是较小的数组的长度。
扩展问题
在面试或者工作学习中，可能会有进一步的问题。
-
问：为什么要对孩子的胃口值和饼干的尺寸进行排序？
答： 对孩子和饼干进行排序的目的是为了更有效地匹配饼干和孩子。通过排序，我们可以在一次遍历中完成所有匹配，而无需额外的操作。这样做还可以使得算法更简洁高效。
-
问：这个算法的时间复杂度是多少？
答： 这个算法的时间复杂度是 O(n log n)，其中 n 是较小的数组的长度。这是因为在排序阶段需要对数组进行排序，而排序算法的时间复杂度通常是 O(n log n)，而后面的单次遍历操作的时间复杂度为 O(n)。
-
问：有没有其他方法来解决这个问题？
答： 是的，还可以使用其他方法来解决这个问题，例如递归、动态规划等。但是在这个问题中，贪心算法是一种简单而有效的解决方法，可以在 O(n log n) 的时间复杂度内得到解决。
-
问：如果孩子或饼干的数量非常大，会对这个算法的性能有什么影响？
答： 如果孩子或饼干的数量非常大，可能会导致排序操作的时间开销变得非常显著。此时，选择更适合大规模数据的排序算法（如快速排序）可能是一个更好的选择。另外，在极端情况下，可能需要考虑优化算法以减少排序的时间复杂度，或者使用并行化技术来加速排序过程。
