iOS LeetCode ☞ 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 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 <= 20000 <= hi <= 10⁶0 <= ki < people.length题目数据确保队列可以被重建 解题思路

当每个人的身高都不相同时，如果我们将他们按照身高从小到大进行排序，那么就可以很方便地还原出原始的队列了。

为了叙述方便，我们设人数为 n，在进行排序后，它们的身高依次为 h0, h1，…，h(n - 1) ，且排在第 i 个人前面身高大于 hi 的人数为 ki。如果我们按照排完序后的顺序，依次将每个人放入队列中，那么当我们放入第 i 个人时：

第 0, ⋯, i - 1 个人已经在队列中被安排了位置，并且他们无论站在哪里，对第 i 个人都没有任何影响，因为他们都比第 i 个人矮；

而第 i + 1, ⋯, n - 1 个人还没有被放入队列中，但他们只要站在第 i 个人的前面，就会对第 i 个人产生影响，因为他们都比第 i 个人高。

如果我们在初始时建立一个包含 n 个位置的空队列，而我们每次将一个人放入队列中时，会将一个「空」位置变成「满」位置，那么当我们放入第 i 个人时，我们需要给他安排一个「空」位置，并且这个「空」位置前面恰好还有 ki 个「空」位置，用来安排给后面身高更高的人。也就是说，第 i 个人的位置，就是队列中从左往右数第 k(i + 1) 个「空」位置。

那么如果有身高相同的人，上述 ki 定义中的大于就与题目描述中要求的大于等于不等价了，此时应该怎么修改上面的方法呢？我们可以这样想，如果第 i 个人和第 j 个人的身高相同，即 hi = hj，那么我们可以把在队列中处于较后位置的那个人的身高减小一点点。换句话说，对于某一个身高值 h，我们将队列中第一个身高为 h 的人保持不变，第二个身高为 h 的人的身高减少 δ，第三个身高为 h 的人的身高减少 2δ，以此类推，其中 δ 是一个很小的常数，它使得任何身高为 h 的人不会与其它（身高不为 h 的）人造成影响。

如何找到第一个、第二个、第三个身高为 h 的人呢？我们可以借助 k 值，可以发现：当 hi = hj 时，如果 ki > kj，那么说明 i 一定相对于 j 在队列中处于较后的位置（因为在第 j 个人之前比他高的所有人，一定都比第 i 个人要高），按照修改之后的结果，hi 略小于 hj，第 i 个人在排序后应该先于第 j 个人被放入队列。因此，我们不必真的去对身高进行修改，而只需要按照 hi 为第一关键字升序，ki 为第二关键字降序进行排序即可。此时，具有相同身高的人会按照它们在队列中的位置逆序进行排列，也就间接实现了上面将身高减少 δ 这一 *** 作的效果。

这样一来，我们只需要使用一开始提到的方法，将第 i 个人放入队列中的第 k(i + 1) 个空位置，即可得到原始的队列。

代码

	// 406. 根据身高重建队列
    func reconstructQueue(_ people: [[Int]]) -> [[Int]] {
        
        let newPeople = people.sorted { person1, person2 in
            if person1[0] != person2[0] {
                return ((person1[0] - person2[0]) < 0)
            } else {
                return ((person2[1] - person1[1]) < 0)
            }
        }
        
        let n = newPeople.count
        var ans = [[Int]](repeating: [Int](repeating: 0, count: 0), count: n)
        for person in newPeople {
            var spaces = person[1] + 1
            for i in 0..<n {
                if ans[i].count == 0 {
                    spaces -= 1
                    if spaces == 0 {
                        ans[i] = person
                        break
                    }
                }
            }
        }
        
        return ans
    }