406·根据身高重建队列·贪心
2023-09-27 14:26:29 时间
链接:https://leetcode.cn/problems/queue-reconstruction-by-height/solution/chun-c-by-xun-ge-v-di20/
来源:力扣(LeetCode)
题目
示例
思路
「贪心算法」的问题需要满足的条件:
- 最优子结构:规模较大的问题的解由规模较小的子问题的解组成,规模较大的问题的解只由其中一个规模较小的子问题的解决定;
- 无后效性:后面阶段的求解不会修改前面阶段已经计算好的结果;
- 贪心选择性质:从局部最优解可以得到全局最优解。
解题思路
题目描述:整数对 (h, k) 表示,其中 h 是这个人的身高,k 是排在这个人前面且身高大于或等于 h 的人数。
套路:一般这种数对,还涉及排序的,根据第一个元素正向排序,根据第二个元素反向排序,或者根据第一个元素反向排序,根据第二个元素正向排序,往往能够简化解题过程。
在本题目中,我首先对数对进行排序,先对数对按照数对的元素 1 降序排序,然后按照数对的元素 2 大体升序排序插入queue数组中。原因是,按照元素 1 进行降序排序,对于每个元素,在其之前的元素的个数,就是大于等于他的元素的数量,而按照第二个元素升序排序插入,保证正确性。
具体实现:
我们先用快速排序对数组p按元素1降序排序,然后申请一个额外数组记录数组p中元素下标对应应该插入到queue中的什么位置,我们先对插入位置进行确定,在最后插入,因为数组p是按元素1降序排列,而我们需要按元素2的升序插入所以需要对数对位置进行频繁的调整,先记录插入位置方便调整位置
代码
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int cmp(const void*_a,const void*_b){
int *a = *(int**)_a, *b = *(int**)_b;
return a[0] == b[0] ? a[1] - b[1] : b[0] - a[0];
}
int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes){
int ** queue = (int **)malloc(sizeof(int *) * peopleSize);
*returnSize = peopleSize;
*returnColumnSizes = malloc(sizeof(int) * peopleSize);
for(int i=0;i<peopleSize;i++){
(*returnColumnSizes)[i]=2;
queue[i] = malloc(sizeof(int) * 2);
}
int q[peopleSize];//初始化一些变量
qsort(people, peopleSize, sizeof(int *), cmp);//按元素1降序
for(int i = 0; i <peopleSize; i++)//排列插入位置
{
q[i] = people[i][1];//q[i]表示p数组中第i的数对,在q数组的插入的位置
if(q[i] < i)//如果p[i]<i的话,相当于往前面插队了,在p[i]后的人位置都得+1
{
for(int j = 0; j < i; j++)
{
if(q[j] >= q[i])
{
q[j]++;
}
}
}
}
for(int i = 0; i < peopleSize; i++)
{
queue[q[i]][0] = people[i][0];
queue[q[i]][1] = people[i][1];
}
return queue;
}
时间空间复杂度