LI@NG

Leetcode 455 Assign Cookies

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

思路:

1,暴力破解,挨个枚举,时间复杂度O(n!)

2, 排序后贪心O(n)

两个数组排序后,以children的为基点遍历,与此同时,对应比较cookies数组中相应的值,如果比cookies数组中小,则跳过。

代码:

function sortNumber(a, b) {
	return a - b;
}

var findContentChildren = function(g, s) {
	const sortedChildren = g.sort(sortNumber);
	const sortedCookies = s.sort(sortNumber);
	let i = 0;
	let count = 0;
	for (var key in sortedChildren) {
		while (sortedChildren[key] > sortedCookies[i] && i < sortedCookies.length) {
			i++;
		}

		if (i < sortedCookies.length) {
			count++;
			i++;
		}
	}

	return count;
};

findContentChildren([10, 9, 8, 7], [5, 6, 7, 8]);