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

請(qǐng)你重新構(gòu)造并返回輸入數(shù)組?people 所表示的隊(duì)列。返回的隊(duì)列應(yīng)該格式化為數(shù)組 queue ，其中 queue[j] = [hj, kj] 是隊(duì)列中第 j 個(gè)人的屬性（queue[0] 是排在隊(duì)列前面的人）。

示例 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]]
解釋：
編號(hào)為 0 的人身高為 5 ，沒(méi)有身高更高或者相同的人排在他前面。
編號(hào)為 1 的人身高為 7 ，沒(méi)有身高更高或者相同的人排在他前面。
編號(hào)為 2 的人身高為 5 ，有 2 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 0 和 1 的人。
編號(hào)為 3 的人身高為 6 ，有 1 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 1 的人。
編號(hào)為 4 的人身高為 4 ，有 4 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 0、1、2、3 的人。
編號(hào)為 5 的人身高為 7 ，有 1 個(gè)身高更高或者相同的人排在他前面，即編號(hào)為 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構(gòu)造后的隊(duì)列。
示例 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]]
?

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

思路：

題目給了若干個(gè)數(shù)組，數(shù)組的第一個(gè)參數(shù)是第i個(gè)人的身高，第二個(gè)參數(shù)是第i個(gè)人前面有幾個(gè)比自己高的人，根據(jù)題目要求，可以想到按照每個(gè)人的身高從高到低排序，再依次遍歷每個(gè)人的第二個(gè)參數(shù)k，之所以先根據(jù)人的身高從低到高排序是為了遍歷到某人的k值時(shí)直接將其移到第k個(gè)位置，因?yàn)樯砀呤菑母叩降团诺?#xff0c;所以移到數(shù)組下標(biāo)為k的位置那么他前面就剛好有k個(gè)比他高的人，即使再向后。

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

輸入：?????? [[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]]

預(yù)期結(jié)果：[[3,0],[6,0],[7,0],[5,2],[3,4],[5,3],[6,2],[2,7],[9,0],[1,9]]

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

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進(jìn)行插值

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插到對(duì)應(yīng)的序號(hào)}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插到對(duì)應(yīng)的序號(hào)}return queue.toArray(new int[people.length][2]);}
}

?