假設有打亂順序的一群人站成一個隊列，數(shù)組 people 表示隊列中一些人的屬性（不一定按順序）。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ，前面 正好 有 ki 個身高大于或等于 hi 的人。

請你重新構造并返回輸入數(shù)組?people 所表示的隊列。返回的隊列應該格式化為數(shù)組 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]]
?

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/queue-reconstruction-by-height
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。

思路：

題目給了若干個數(shù)組，數(shù)組的第一個參數(shù)是第i個人的身高，第二個參數(shù)是第i個人前面有幾個比自己高的人，根據(jù)題目要求，可以想到按照每個人的身高從高到低排序，再依次遍歷每個人的第二個參數(shù)k，之所以先根據(jù)人的身高從低到高排序是為了遍歷到某人的k值時直接將其移到第k個位置，因為身高是從高到低排的，所以移到數(shù)組下標為k的位置那么他前面就剛好有k個比他高的人，即使再向后。

那分析到這里可以意識到，一開始遺漏掉了題目里的另一個條件，題目給的k的含義是排在當前位置的人前面有k個大于或等于當前位置人的身高的數(shù)量，開始沒注意到這個等于的條件導致一些用例測試錯誤。

輸入：?????? [[9,0],[7,0],[1,9],[3,0],[2,7],[5,3],[6,0],[3,4],[6,2],[5,2]]

輸出：?????? [[3,0],[6,0],[7,0],[5,2],[3,4],[6,2],[5,3],[2,7],[9,0],[1,9]]

預期結果：[[3,0],[6,0],[7,0],[5,2],[3,4],[5,3],[6,2],[2,7],[9,0],[1,9]]

?找到問題之后，將相同身高的人按照其k值的大小從低到高排序便解決了這個問題。

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] > o2[0] ? -1 : (o1[0] == o2[0])&&(o1[1] < o2[1]) ? -1 : 1;}});int length = people.length;for (int i = 0; i < length; i++) {insertPeople(i, people[i][1], people);}return people;}public void insertPeople(int sour, int dest, int[][] people) {int sourH = people[sour][0];int sourK = people[sour][1];for (int i = sour; i > dest; --i) {people[i][0] = people[i - 1][0];people[i][1] = people[i - 1][1];}people[dest][0] = sourH;people[dest][1] = sourK;}
}

?另一種排序的方法

Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

?

方法二：List進行插值

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, ((o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]));List<int[]> queue = new ArrayList<int[]>();int length = people.length;for(int[] p:people){queue.add(p[1],p);//根據(jù)k把p插到對應的序號}return queue.toArray(new int[people.length][2]);}
}

優(yōu)化排序

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0] > o2[0] ? -1 : (o1[0] == o2[0]) && (o1[1] < o2[1]) ? -1 : 1;}});List<int[]> queue = new ArrayList<int[]>();int length = people.length;for(int[] p:people){queue.add(p[1],p);//根據(jù)k把p插到對應的序號}return queue.toArray(new int[people.length][2]);}
}

?