[LeetCode]Queue Reconstruction by Height

如果我们按照高度从高到低(如果高度相同的话，第二个数更小的人排前面)考虑所有的人，当我们处理排序后第i个人的时候，前面高度大于等于他的i - 1个人我们已经考虑过了，假设其要求前面高度大于等于他的人有k个，我们只需要将这个人在已经考虑过的所有人排在k + 1即可。因为后面的人只有两种情况：

• 高度和people[i]相等，但根据我们sort的规则，如果高度相同的话，第二个数更小的人排前面。所以其插入后也肯定排在people[i]后面。
• 高度小于people[i]，那么更不会影响people[i]排位的合理性。其前面仍然会有k个人比他高，这点不会变。

所以如果我们按照这个顺序考虑每个人people[i]，结束时每个人的顺位仍然是合理的。按照这个方法的话，其实就类似于insertion sort。时间复杂度O(n^2)，空间复杂度O(1)。代码如下：

	class Solution {
	public:
	vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
	int len = people.size();
	auto comp = [](const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.first == rhs.first ? lhs.second < rhs.second: lhs.first > rhs.first; };
	sort(people.begin(), people.end(), comp);
	for (int i = 1; i < len; ++i)
	{
	auto person = people[i];
	int j = i;
	while (j > person.second)
	{
	swap(people[j], people[j - 1]);
	--j;
	}
	}
	return people;
	}
	};

view raw Queue Reconstruction by Height.cpp hosted with ❤ by GitHub

另外一种方法会用到segment tree，关于segment tree的介绍可以参考这篇文章。那么我们要存什么，又查询什么呢？如果我们按照高度从低到高排序(如果高度相同的话，第二个数更大的人排前面)，我们从左到右依次考虑每一个人p = [i, j]，我们只需要把p插入到从左向右的第j + 1个available的slot即可，因为后面的人高度都是大于等于p的，而且前面的空着的j个slot都会填满，所以p最后会满足条件。所以对于长度为n的输入数组，segment tree要存的就是位于index i的slot是否被填上了。如果我们用1表示没填上，0表示填上，这虽然有点反直觉，但是我们如果找到第一个presum = j + 1的位置，并且没有被填上，这个就是p所要去的位置。所以segment tree的每个node存的是这个node所表示的区间[start, end]还有多少slot是available的，我们查询从左到右第k个available的slot的时候就运用binary search + presum即可。时间复杂度为O(n * log n)，空间复杂度O(n)，代码如下：

	struct Node
	{
	int start, end;
	//for leaf node, 1 represetns not occupied, 0 represent occupied
	//for non-leaf node region sum represent how many slots are available in this region
	int val;
	Node* left, *right;
	Node(int s, int e)
	{
	start = s;
	end = e;
	val = 1;
	left = nullptr;
	right = nullptr;
	}
	void build()
	{
	if (start == end)return;
	getLeft()->build();
	getRight()->build();
	val = getLeft()->val + getRight() -> val;
	}
	//binary search to find key-th available slot
	int queryAndUpdate(int key)
	{
	if (start == end)
	{
	val = 0;
	return start;
	}
	int leftSum = getLeft()->val;
	int idx = -1;
	if (leftSum >= key)idx = getLeft()->queryAndUpdate(key);
	else idx = getRight()->queryAndUpdate(key - leftSum);
	val = getLeft()->val + getRight()->val;
	return idx;
	}
	Node* getLeft()
	{
	if (start == end)return nullptr;
	int mid = start + (end - start) / 2;
	if (!left)left = new Node(start, mid);
	return left;
	}
	Node* getRight()
	{
	if (start == end)return nullptr;
	int mid = start + (end - start) / 2;
	if (!right)right = new Node(mid + 1, end);
	return right;
	}
	};
	class Solution {
	public:
	vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
	int len = people.size();
	if (!len)return{};
	auto comp = [](const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.first == rhs.first ? lhs.second > rhs.second : lhs.first < rhs.first; };
	sort(people.begin(), people.end(), comp);
	Node* node = new Node(0, len - 1);
	node->build();
	vector<pair<int, int>> res(len);
	for (int i = 0; i < len; ++i)
	{
	int ans = node->queryAndUpdate(people[i].second + 1);
	res[ans] = people[i];
	}
	return res;
	}
	};

view raw Queue Reconstruction by Height_segment_tree.cpp hosted with ❤ by GitHub