题目详情
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height
解法思路
思路一：
思路分析
- 考虑到大多数情况下，第二维数据（身高比该人高且在该人前面的数量）越小，应该排名越靠前。首先将people数组按照第二维排序，接着第二维相同的按照第一维排序；
- 接着进行单向比较，从第二个元素开始（排完序后可以确保第一个一定是排在第一位的），从头开始比较，如果经过j各元素后，比该元素大的元素已经大于该元素第二维数值，则把这个元素插在第people[i]+1个比该元素大的元素前面，若插在其他地方会影响已经排序好的结果，插在比它大的前一位则不会；若一直遍历到元素本身，也没超过元素的第二维数值，则不更新元素位置；
- 遍历整个数组，最后输出。
代码
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,new Comparator<int [] >(){
public int compare(int [] a1,int [] a2) {
if(a1[1]>a2[1]) {return 1;}
else if(a1[1]<a2[1]) {return -1;}
else {return Integer.compare(a1[0], a2[0]);}
}
});
List<int[]> list1 = new ArrayList();
for(int[] a : people){
list1.add(a);
}
int flag = 1;
int[] nextele = new int[2];
for(int i = 1;i<list1.size();i++){
if(i!=list1.size()-1){
nextele = list1.get(flag+1);}
int num = 0;
int j = 0;
int[] temp1 = list1.get(flag);
while(j<flag&&num<temp1[1]+1){
int[] temp = list1.get(j);
if(temp[0]>=temp1[0]){
num++;
}
if(num!=temp1[1]+1){j++;}
}
if((j)!=flag){
list1.remove(temp1);
list1.add(j,temp1);
}
flag = list1.indexOf(nextele);
}
int[][] result = new int[people.length][people[0].length];
for(int i = 0;i<list1.size();i++){
int[] temp = list1.get(i);
result[i][0] = temp[0];
result[i][1] = temp[1];
}
return result;
}
}
方案分析
空间复杂度：该方法主要需要一个LinkedList来存储数组，以及一个result数组来存储最终结果；
时间复杂度：笔者本准备使用LinkedList来降低插入和删除的时间复杂度，但是代码中存在大量的获取元素值操作，此操作使用ArrayList最快，换成ArrayList后速度提升；整体时间复杂度为O(n^3)，方案较为复杂。
思路二
思路分析
* 解题思路：先排序再插入
* 1.排序规则：按照先H高度降序，K个数升序排序
* 2.遍历排序后的数组，根据K插入到K的位置上
*
* 核心思想：高个子先站好位，矮个子插入到K位置上，前面肯定有K个高个子，矮个子再插到前面也满足K的要求
*
* 具体解析：
* 将数组按上述规则排序后，最高的且K最小的在前面，相同的高度，
* 必然K小的在前面。排完后，定义一个列表，将后续元素插入列表，
* 插入规则为，插在第K个位置。因为矮个子的插入，不会影响前面
* 已经排好的高个子的K值。
作者：pphdsny
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/406-gen-ju-shen-gao-zhong-jian-dui-lie-java-xian-p/
来源：力扣（LeetCode）
代码
class Solution{
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);
LinkedList<int[]> list = new LinkedList<>();
for (int[] i : people) {
list.add(i[1], i);
}
return list.toArray(new int[list.size()][2]);
}
}
方案分析
* 空间复杂度：改方案定义了一个列表用来存储插入的元素，
* 因为只有add()操作，所以定义为LinkedList
* 时间复杂度：O(nlogn)左右，在于排序部分，后面插入只
* 有O(n)，排序部分第一步排序O(nlogn)，第二步排序视第
* 一步而定
* 该方案非常巧妙，在于发现矮个子插在高个子前面不影响
* 高个子K值，时间复杂度较低
|