LeetCode 406. 根据身高重建队列 JAVA 回看

拼搏现实的明天。 2022-12-21 10:56 112阅读 0赞

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

示例
    
    输入:
    [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    
    输出:
    [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
1、先将pople数组按照身高从低到高排序，如果身高相同的情况下，按照站在其前面的人数，从多到少进行排序（后续讲解为什么要这样做）。  
2、遍历people数组，新建res数组用来保存结果，people【i】【1】表示第i个人前面有k个人比他高，所以在res数组中，第i个人应该放在第k+1个位置，以便前k个位置让比他高的人来站，保证他前面有比他高的k个人，依次遍历即可得到结果。  
那么现在就来讲解一下为什么要按照步骤1进行排序：

1.  people数组按照身高从低到高排序，是模拟出正常队列排序时的样子，就是应该从高到低，从而方便理解。
2.  people【i】【1】按照从多到少的排序的目的是因为题目要求的people【i】【1】表示的是k是排在这个人前面且身高大于或等于h的人数，注意这里有等于，按照我们的排序方法和例子来看，【7,0】，【7,1】这两个数如果按照这样的顺序进行排列，那么【7,0】会将res的res【0】占领，而当【7,1】想要插入时，会发现是没有空可以让其插入的。
3.  在这种情况下，为了解决，我们可以将【7,0】，【7,1】给想象成【7.1,0】，【7,1】，即people【i】【0】相等的情况下，我们可以把people【i】【1】小的想象的要稍微高一点，以便people【i】【1】大的可以提前插空，预留出位置使得【7,0】可以进行插入，从而完成任务。

class Solution {
        
        public int[][] reconstructQueue(int[][] people) {
        
            Arrays.sort(people,new Comparator<int[]>(){
        
                public int compare(int people1[],int people2[]){
        
                    if(people1[0]!=people2[0]) return people1[0]-people2[0];
                    else return people2[1]-people1[1];
                }
            });
            int res[][]=new int[people.length][];
            for(int []p:people){
        
                int space=p[1]+1;
                for(int i=0;i<people.length;i++){
        
                    if(res[i]==null){
        
                        space--;
                        if(space==0) 
                        {
        
                            res[i]=p;
                            break;
                        }  
                    }
                }
            }
            return res;
        }
    }