根据身高重建队列

编号为 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]] 是重新构造后的队列。

编号为 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]]

输入：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 a, constvector< int> b) {

if(a[ 0] == b[ 0]) returna[ 1] < b[ 1];

returna[ 0] > b[ 0];

}

vector< vector< int>> reconstructQueue( vector< vector< int>>& people) {

sort (people.begin, people.end, cmp);

list< vector< int>> que; // list底层是链表实现，插入效率比vector高的多

for( inti = 0; i < people.size; i++) {

intposition = people[i][ 1]; // 插入到下标为position的位置

std:: list< vector< int>>::iterator it = que.begin;

while(position--) { // 寻找在插入位置

it++;

}

que.insert(it, people[i]);

}

returnvector< vector< int>>(que.begin, que.end);

}

};

时间复杂度O(nlogn + n^2)

空间复杂度O(n)

时间复杂度O(nlogn + n^2)

空间复杂度O(n)

大家可以把两个版本的代码提交一下试试，就可以发现其差别了！

关于本题使用数组还是使用链表的性能差异，我在贪心算法：根据身高重建队列（续集）中详细讲解了一波

总结

关于出现两个维度一起考虑的情况，我们已经做过两道题目了，另一道就是135. 分发糖果。

其技巧都是确定一边然后贪心另一边，两边一起考虑，就会顾此失彼。

这道题目可以说比135. 分发糖果难不少，其贪心的策略也是比较巧妙。

最后我给出了两个版本的代码，可以明显看是使用C++中的list（底层链表实现）比vector（数组）效率高得多。

对使用某一种语言容器的使用，特性的选择都会不同程度上影响效率。

所以很多人都说写算法题用什么语言都可以，主要体现在算法思维上，其实我是同意的但也不同意。

对于看别人题解的同学，题解用什么语言其实影响不大，只要题解把所使用语言特性优化的点讲出来，大家都可以看懂，并使用自己语言的时候注意一下。

对于写题解的同学，刷题用什么语言影响就非常大，如果自己语言没有学好而强调算法和编程语言没关系，其实是会误伤别人的。

这也是我为什么统一使用C++写题解的原因，其实用其他语言java、python、php、go啥的，我也能写，我的Github上也有用这些语言写的小项目，但写题解的话，我就不能保证把语言特性这块讲清楚，所以我始终坚持使用最熟悉的C++写题解。

而且我在写题解的时候涉及语言特性，一般都会后面加上括号说明一下。没办法，认真负责就是我，哈哈。

其他语言版本JavaclassSolution{

publicint[][] reconstructQueue( int[][] people) {

// 身高从大到小排（身高相同k小的站前面）

Arrays.sort(people, (a, b) -> {

if(a[ 0] == b[ 0]) returna[ 1] - b[ 1];

returnb[ 0] - a[ 0];

});

LinkedList< int[]> que = newLinkedList;

for( int[] p : people) {

que.add(p[ 1],p);

}

returnque.toArray( newint[people.length][]);

}

}

PythonclassSolution:

defreconstructQueue(self, people: List[List[int]])-> List[List[int]]:

# 先按照h维度的身高顺序从高到低排序。确定第一个维度

# lambda返回的是一个元组：当-x[0](维度h）相同时，再根据x[1]（维度k）从小到大排序

people.sort(key= lambdax: (-x[ 0], x[ 1]))

que = []

# 根据每个元素的第二个维度k，贪心算法，进行插入

# people已经排序过了：同一高度时k值小的排前面。

forp inpeople:

que.insert(p[ 1], p)

returnque

GofuncreconstructQueue(people [][] int) [][] int{

//先将身高从大到小排序，确定最大个子的相对位置

sort.Slice(people, func(i,j int)bool {

ifpeople[i][ 0]==people[j][ 0]{

returnpeople[i][ 1]people[j][ 0] //这个只是确保身高按照由大到小的顺序来排，并不确定K是按照从小到大排序的

})

//再按照K进行插入排序，优先插入K小的

result := make([][] int, 0)

for_, info := rangepeople {

result = append(result, info)

copy(result[info[ 1] + 1:], result[info[ 1]:]) //将插入位置之后的元素后移动一位（意思是腾出空间）

result[info[ 1]] = info //将插入元素位置插入元素

}

returnresult

}

//链表法

funcreconstructQueue(people [][] int) [][] int{

sort.Slice(people, func(i,j int) bool{

ifpeople[i][ 0]==people[j][ 0]{

returnpeople[i][ 1]people[j][ 0]

})

l:=list.New //创建链表

fori:= 0;i< len(people);i++{

position:=people[i][ 1]

mark:=l.PushBack(people[i]) //插入元素

e:=l.Front

forposition!= 0{ //获取相对位置

position--

e=e.Next

}

l.MoveBefore(mark,e) //移动位置

}

res:=[][] int{}

fore:=l.Front;e!= nil;e=e.Next{

res= append(res,e.Value.([] int))

}

returnres

}

JavavarreconstructQueue = function( people) {

letqueue = []

people.sort( ( a, b ) => {

if(b[ 0] !== a[ 0]) {

returnb[ 0] - a[ 0]

} else{

returna[ 1] - b[ 1]

}

})

for( leti = 0; i < people.length; i++) {

queue.splice(people[i][ 1], 0, people[i])

}

returnqueue

};

--- EOF ---

推荐↓↓↓返回搜狐，查看更多