leetcode455.AssignCookies（C语言，堆排序）28

贴原题&＃xff1a;

Assume you are an awesome parent and want to give your children some COOKIEs. But, you should give each child at most one COOKIE. Each child i has a greed factor gi, which is the minimum size of a COOKIE that the child will be content with; and each COOKIE j has a size sj. If sj >&＃61; gi, we can assign the COOKIE j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note: You may assume the greed factor is always positive. You cannot assign more than one COOKIE to one child.

Example 1: Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 COOKIEs. The greed factors of 3 children are 1, 2, 3. And even though you have 2 COOKIEs, since their size is both 1, you could only make the child whose greed factor is 1 content. You need to output 1.

Example 2: Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 COOKIEs. The greed factors of 2 children are 1, 2. You have 3 COOKIEs and their sizes are big enough to gratify all of the children, You need to output 2.

解析&＃xff1a;
　　本题的题目说的有点复杂&＃xff0c;简单来说就是给出两个数组&＃xff0c;求数组&＃xff12;big enough于数组&＃xff12;元素的个数。换言之&＃xff0c;就是求数组&＃xff12;中元素>&＃61;数组&＃xff11;中元素的个数。
　　我的思路很简单&＃xff0c;就是把两个数组从小到大排序&＃xff0c;然后依次比较各位元素的大小&＃xff0c;如果big enough则计数器加一&＃xff0c;否则换数组&＃xff12;中下一个较大的值与之比较&＃xff0c;直到其中一个数组的元素都比较完。

&＃xff23;代码&＃xff1a;

void heapAjust(int* array, int size, int root)//堆调整&＃xff0c;构建最大顶堆
{int left&＃61;2*root;int right&＃61;left&＃43;1;int largest&＃61;root;if(leftarray&＃43;left)>*(array&＃43;largest)){largest&＃61;left;}if(rightarray&＃43;right)>*(array&＃43;largest)){largest&＃61;right;}if(largest!&＃61;root){*(array&＃43;largest)&＃61;*(array&＃43;largest)^*(array&＃43;root);*(array&＃43;root)&＃61;*(array&＃43;largest)^*(array&＃43;root);*(array&＃43;largest)&＃61;*(array&＃43;largest)^*(array&＃43;root);heapAjust(array, size, largest);}
}
void heapSort(int* array, int size)//堆排序
{for(int i&＃61;size/2; i>&＃61;0; i--){heapAjust(array, size, i);}for(int i&＃61;size-1; i>0; i--){*array&＃61;*array^*(array&＃43;i);*(array&＃43;i)&＃61;*array^*(array&＃43;i);*array&＃61;*array^*(array&＃43;i);heapAjust(array, i, 0);}
}
int findContentChildren(int* g, int gSize, int* s, int sSize) {heapSort(g, gSize);heapSort(s, sSize);int cnt&＃61;0;//计数器int i&＃61;0, j&＃61;0;while(iif(*(g&＃43;i)<&＃61;*(s&＃43;j))//big enough{cnt&＃43;&＃43;;//计数器加一i&＃43;&＃43;;//继续比较下一个j&＃43;&＃43;;}else//否则用s数组的下一个较大值与当前g[i]做比较{j&＃43;&＃43;;}}return cnt;
}