[LC-406][chapter2][Greedy Algorithm] Queue Reconstruction by Height 根据身高重建队列

[wrlssqi]

英文链接： https://leetcode.com/problems/queue-reconstruction-by-height/

中文描述： 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

示例 1：

输入： people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出： [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释： 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入： people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出： [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

提示：

• 1 <= people.length <= 2000
• 0 <= hi <= 106
• 0 <= ki < people.length
• 题目数据确保队列可以被重建

大白话解释： 其实就是，有一个排好队的队伍，每个队伍的每个人有一个身高h。然后就可以知道每个人的前面，有多少身高大于等于ta的人数k，即[h, k]代表的含义。然后，把这个排好的队伍随机打散，就变成了题目里给的 queue数组。我们的任务是，根据 queue的内容，重新把各个元素按照原来的队伍顺序排好。

---

解法1: 我们可以知道，最终重建好的队列，具有以下特征：

1. 具有相同k值的元素，必定h值小的在前，h值大的在后。设有A B两个人，他们具有相同的k值，且ha >hb，那么A一定在B后面。反证：如果A在B前面，A的前面有k个人身高大于等于A。B身高又小于等于A，那么B的k值至少也是 ka+1，A和B的k值一定不相等。
2. k值较小的元素，更可能分布在队伍的前面。k值较大的元素，更可能分布在队伍的后面。且队伍的第一个，一定是k值为0，且在k值为0的所有元素中，h值最小的元素
3. 不会存在两个元素，他们的h和k值都相等。

然后就有了其实我也没完全想清楚为什么会正常工作的解法。。。当时是凭直觉猜的，这么着也许能行😂 那么这个神奇的方法如下：

1. 把给定的数组，按照k值从小到大排列。对于具有同样k值的元素，按照h值从小到大排列。以上面的示例一为例，排列后，数组变为 [[5,0],[7,0],[6,1],[7,1],[5,2],[4,4]]
2. 跳过k值为0的元素，从第一个k=1的元素开始，获取该元素（current element）的特征(h值和k值)。这个例子里，是[6,1]元素。
3. 然后再从0索引开始，比较索引的元素和当前元素的h值的大小关系，记录h值大于等于当前元素h值的个数
4. 一旦大于等于当前元素的个数等于当前元素的k值，说明k值需要插在当前比较索引元素的后面。注意，这个插入操作只会更改从0索引到当前元素的分布，不会更改当前元素后面元素的位置。[6,1]元素，6比[5,0]里的5大，比[7,0]里的7小，所以[6,1]要放在[7,0]后面。操作完成后，数组变为 [[5,0],[7,0],[6,1],[7,1],[5,2],[4,4]]
5. 记录下当前元素插入的位置，后续处理元素如果k值等于当前元素，h值必大于当前元素，则后续的元素必定要放在当前元素后面。如果后续处理元素的k值和当前元素不相等，则没有这个约束。
6. 继续处理当前元素的后续元素，重复2到5步骤。 按照例子来说，开始处理[7,1]元素。然后遍历时，第二个[7,0]元素的7>=7,k值已经等于1了。但由于[6,1]元素在索引2位置，[7,1]至少也要在[6,1]之后，所以处理[7,1]元素后，变为[[5,0],[7,0],[6,1],[7,1],[5,2],[4,4]]。 继续处理[5,2]元素，变为[[5,0],[7,0],[5,2],[6,1],[7,1],[4,4]]。继续处理[4,4]，变为[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

还是看代码吧，感觉还是看代码更好理解一些😂 代码:

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {

    //先把输入的人，从小到达排序。主序为 他前面的人数 kj，次序为他的身高 hj
    sort(people.begin(), people.end(), [](const vector<int> &a, const vector<int> &b)
         {
             if (a[1] < b[1])
             {
                 return true;
             }
             else if (a[1] > b[1])
             {
                 return false;
             }
             else
             {
                 return a[0] < b[0];
             }
         });

    int atleast_idx = 0; //当前的元素至少要放在这个位置后面
    int current_idx = 0; //当前的循环，正在处理的元素，其在排序过的people vector中的位置

    int prev_k = 0;         //保存上一个元素的k值
    int compare_idx = 0;    //从头开始索引元素，和当前的元素进行比较
    int highover_count = 0; //记录从前往后开始，有多少人身高 大于等于当前的元素
    const int peoplesize = people.size();

    vector<int> tempsave;

    while (current_idx < peoplesize)
    {
        //如果当前的值的k不为0，则开始后续操作，否则不做任何操作
        if (people[current_idx][1] > 0)
        {
            if (people[current_idx][1] != prev_k)
            {
                //当前处理的元素的k和上一个元素的不一致了的话，则需要重新更新atleast_idx 到0
                atleast_idx = 0;
            }

            prev_k = people[current_idx][1]; //保存一下当前的k值，供下一个循环使用
            highover_count = 0;              //清零
            compare_idx = 0;
            for (compare_idx = 0; compare_idx < current_idx; compare_idx++)
            {
                if (people[compare_idx][0] >= people[current_idx][0])
                {
                    highover_count++;
                }

                if (highover_count == people[current_idx][1] && compare_idx >= atleast_idx)
                    break;
            }

            if (compare_idx < current_idx)
            {
                //跳出循环后的 compare_idx 小于 current_idx 说明找到了位置，但位置需要+1，才是插入位置
                compare_idx++;
            }

            if (compare_idx < current_idx)
            {
                //需要插入的位置和当前元素的位置不一样，则说明需要把元素拿出来并插入  否则不需要做任何操作
                tempsave = people[current_idx];
                for (size_t i = current_idx; i > compare_idx; i--)
                {
                    //把从 compare_idx 到 current_idx的元素往后挪一个位置
                    people[i] = people[i-1];
                }
                people[compare_idx]=tempsave; //把当前元素插入到对应的位置
            }
            atleast_idx = compare_idx; // 更新atleast_idx 位置。后面具有同样k值的元素，至少要在atleast_idx位置之后
        }

        current_idx++;
    }

    return people;
    }
};

复杂度分析： 时间复杂度： 一开始的排序，使用的是stl的sort函数，时间复杂度为O(nlogn)。 后面的共需要处理所有k>=1的元素；每个元素都要索引从0到该元素之间的元素来进行比较操作，虽然当k值条件满足之后，即可停止比较索引。然后还有后续的插入操作时，挪腾元素时的索引操作。是对插入位置到当前元素位置之间所有元素进行操作。比较索引和插入索引一起，正好是当前元素索引值的次数。所以，当输入的数组长度为n时，总的索引次数是1+2+3+...+n ，依等差数列求和公式，有n^2项，所以时间复杂度是O(n^2)，所以总的时间复杂度是O(n^2) 空间复杂度： 由于一直是对给的数组进行操作，额外使用的只有一些数量固定的变量，所以空间复杂度为O(1)。

解法2: 从题目讨论帖子里看到的贼啦简洁的方法。属实把握了问题本质。 影响一个元素的k值的，只会是h值大于等于他的元素。所有h值小于他的元素，不论插在队伍的哪里，都不会影响其k值。 步骤

1. 重新排序给的数组，排序方式为，按照h值从大到小的方式排列。对于h值相同的元素，按照k值从小到大的地方排序。
2. 从头开始索引排序好的元素，然后按照当前元素的k值，作为插入位置，往一个新数组里插

以上面的例1为例： 重排序后，数组变为 [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]] 定义一个新的空数组A，然后[7,0]插入到A的0索引，A变为[[7,0]] [7,1]插入A的1索引处，A变为[[7,0],[7,1]] [6,1]插入A的1索引处，A变为[[7,0],[6,1],[7,1]] [5,0]插入A的0索引处，A变为[[5,0],[7,0],[6,1],[7,1]] [5,2]插入A的2索引处，A变为[[5,0],[7,0],[5,2],[6,1],[7,1]] [4,4]插入A的4索引处，A变为[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

代码如下：

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {

/*
1. Pick out tallest group of people and sort them in a subarray (S). Since there's no other groups of people taller than them, therefore each guy's index will be just as same as his k value.
2. For 2nd tallest group (and the rest), insert each one of them into (S) by k value. So on and so forth.
E.g.
input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
subarray after step 1: [[7,0], [7,1]]
subarray after step 2: [[7,0], [6,1], [7,1]]
*/

        //把输入 优先按照 身高高的最前  然后如果身高相等的，则 k值小的在前的方式排序
        sort(people.begin(), people.end(),[](const vector<int> &p1,const  vector<int> &p2){
            return p1[0] > p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
        });

        vector<vector<int>> sol;
        int n = people.size();
        for (int i = 0; i < n;i++)
        {
            sol.insert(sol.begin() + people[i][1], people[i]);
        }
        return sol;
    }
};

复杂度分析： 时间复杂度： 一开始的排序复杂度为O(nlogn)。后面，需要索引所有元素，然后又执行插入操作。每次插入操作的时间复杂度为O(M+N)，其中M为要插入的元素，这里每次插入1个元素，即M=1. N为要移动的元素的数量，即从插入位置到当前数组的最后位置的元素个数。我们并不知道每个元素的插入位置，所以做最坏的估计，每次都从头插入，则每次插入时，时间复杂度为O(i),i为当前重排数组的大小。又需要插入n次，每次插入时，重排数组的长度递增，i也+1递增，总的时间复杂度依然是一个等差数列求和，也是O(n^2)。故总的时间复杂度为O(n^2)。 空间复杂度： 需要重新申请一个数组，存放重排后的队伍元素。空间复杂度为O(n)。