支付网站建设费的会计分录,照片生成视频制作软件,软件技术专业升本可以升哪些专业,在线商城网站制作假设有打乱顺序的一群人站成一个队列#xff0c;数组 people 表示队列中一些人的属性#xff08;不一定按顺序#xff09;。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi #xff0c;前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 peopl…假设有打乱顺序的一群人站成一个队列数组 people 表示队列中一些人的属性不一定按顺序。每个 people[i] [hi, ki] 表示第 i 个人的身高为 hi 前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 思路
题目给了若干个数组数组的第一个参数是第i个人的身高第二个参数是第i个人前面有几个比自己高的人根据题目要求可以想到按照每个人的身高从高到低排序再依次遍历每个人的第二个参数k之所以先根据人的身高从低到高排序是为了遍历到某人的k值时直接将其移到第k个位置因为身高是从高到低排的所以移到数组下标为k的位置那么他前面就刚好有k个比他高的人即使再向后。
那分析到这里可以意识到一开始遗漏掉了题目里的另一个条件题目给的k的含义是排在当前位置的人前面有k个大于或等于当前位置人的身高的数量开始没注意到这个等于的条件导致一些用例测试错误。 输入 [[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 Comparatorint[]() {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]));Listint[] queue new ArrayListint[]();int length people.length;for(int[] p:people){queue.add(p[1],p);//根据k把p插到对应的序号}return queue.toArray(new int[people.length][2]);}
} 优化排序
class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, new Comparatorint[]() {Overridepublic int compare(int[] o1, int[] o2) {return o1[0] o2[0] ? -1 : (o1[0] o2[0]) (o1[1] o2[1]) ? -1 : 1;}});Listint[] queue new ArrayListint[]();int length people.length;for(int[] p:people){queue.add(p[1],p);//根据k把p插到对应的序号}return queue.toArray(new int[people.length][2]);}
}
