LeetCode OJ 406. Queue Reconstruction by Height

Description

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1,100.

Example

Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解題思路

這個題目的解題方法一開始比較難想到。但是有了想法做起來就很簡單。 隊列中的元素(h,k)表示在這個元素前比h大的元素有k個。題意是要把這樣的元素組成的隊列排序。首先把元素排序：按照h的降序排列，h相等時，按照k的升序排列。然后我們再一個個把元素插入到結(jié)果隊列中。插入的方法是：插入到當(dāng)前隊列下標(biāo)為k的位置。因為我們之前插入的都是比這個元素的h值大的元素，因此當(dāng)前元素的h值就是隊列中所剩下未插入結(jié)果隊列的h值最大的元素了。而且k值是升序排列的，保證了結(jié)果插入的過程中不會越界。 eg. 題目中所給的輸入進行排序后 Input: [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]] 結(jié)果Result首先插入第一個元素[7,0]： Result: [[7,0]] 插入第二個元素[7,1]，在Result中下標(biāo)為1的位置，即偏移量為1： Result: [[7,0], [7,1]] 插入第三個元素[6,1]： Result: [[7,0], [6,1], [7,1]] 插入第四個元素[5,0]： Result: [[5,0], [7,0], [6,1], [7,1]] 插入第五個元素[5,2]： Result: [[5,0], [7,0], [5,2], [6,1], [7,1]] 插入第六個元素[4,4]： Result: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Note:

std::sort函數(shù)是全局的，如果第三個參數(shù)cmp不是靜態(tài)成員函數(shù)或者全局函數(shù)，運行都會報錯。非靜態(tài)函數(shù)是依賴于具體對象的，因此調(diào)用sort函數(shù)時，只能調(diào)用不依賴于對象的靜態(tài)函數(shù)cmp。

代碼

個人github代碼鏈接