LeetCode406：重建身高队列精髓解析

LeetCode406假设有打乱顺序的一群人站成一个队列数组people表示队列中一些人的属性不一定按顺序。每个people[i] [hi, ki]表示第i个人的身高为hi前面正好有ki个身高大于或等于hi的人。请你重新构造并返回输入数组people所表示的队列。返回的队列应该格式化为数组queue其中queue[j] [hj, kj]是队列中第j个人的属性queue[0]是排在队列前面的人。示例 输入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]] 是重新构造后的队列。Python解法从大到小排序class Solution: def reconstructQueue(self, people: List[List[int]]) - List[List[int]]: # 排序规则 # 1. -x[0]身高从大到小降序 # 2. x[1]身高相同k从小到大升序 people.sort(keylambda x: (-x[0], x[1])) res [] # 遍历排好序的每个人 for person in people: h, k person # 直接插入到下标k的位置 res.insert(k, person) return res过程展示步骤 1排序规则先处理高个子身高 h从大到小排序身高相同的两个人k从小到大排序。 原因等高的人互相算 “身高≥自己”k 小的要放前面。步骤 2逐个插入队列按上面排好的顺序依次把每个人插入结果数组的下标 k的位置示例演示1.输入[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]2.排序后插入顺序[7,0]、[7,1]、[6,1]、[5,0]、[5,2]、[4,4]3.逐个插入到下标 k1[7,0] 插 0 号位置 →[[7,0]]2[7,1] 插 1 号位置 →[[7,0],[7,1]]3[6,1] 插 1 号位置 →[[7,0],[6,1],[7,1]]4[5,0] 插 0 号位置 →[[5,0],[7,0],[6,1],[7,1]]5[5,2] 插 2 号位置 →[[5,0],[7,0],[5,2],[6,1],[7,1]]6[4,4] 插 4 号位置 →[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]4.最终队列全部满足每个人的 k 条件这就是题目要求输出的答案。Java解法从大到小排序class Solution { public int[][] reconstructQueue(int[][] people) { // 自定义排序 Arrays.sort(people, (a, b) - { if (a[0] ! b[0]) { return b[0] - a[0]; // 身高降序 } else { return a[1] - b[1]; // k升序 } }); Listint[] list new ArrayList(); for (int[] p : people) { list.add(p[1], p); } return list.toArray(new int[list.size()][]); } }C解法从大到小排序class Solution { public: vectorvectorint reconstructQueue(vectorvectorint people) { sort(people.begin(), people.end(), [](vectorint a, vectorint b){ if (a[0] ! b[0]) return a[0] b[0]; return a[1] b[1]; }); vectorvectorint res; for (auto p : people) { res.insert(res.begin() p[1], p); } return res; } };