力扣406——根据身高重建队列

这道题主要涉及的是找规律和快速排序，优化时需要考虑 Java 中数据结构的特性。

原题

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

注意：

总人数少于1100人。

示例

<code>输入:
[[7,0]
, 
[4,4]
, 
[7,1]
, 
[5,0]
, 
[6,1]
, 
[5,2]
]

输出:
[[5,0]
, 
[7,0]
, 
[5,2]
, 
[6,1]
, 
[4,4]
, 
[7,1]
]/<code>

原题url：https://leetcode-cn.com/problems/queue-reconstruction-by-height/

解题

两次快速排序

拿到这道题目，先想想规律。关注的重点应该在于这句话：k是排在这个人前面且身高大于或等于h的人数。

所以一般肯定是 h 大的在前面，但也需要考虑 k，当 h 相同时，肯定是 k 越小，越在前面。

这样也就涉及到了排序，排序中时间复杂度低的也就是快速排序和归并排序。本题并不需要考虑稳定性，因为原始的数组并没有规律，且并没有涉及原始数组的顺序，所以两种排序用哪个都可以。但考虑到快速排序写起来更简单，因此就采用它。

我的思路是：

• 先针对 h ，如果 h 越大，则越靠前(也就是降序)，做一次快速排序。
• 如果 h 相同时，再针对 k，如果 k 越小，则越靠前(也就是升序)，再做一次快速排序。
• 利用自定义的 TreeNode 结构，也就是单向链表，根据 k 进行插入。
• 遍历单向链表，输出最终结果

接下来看看代码：

<code>
class
 
Solution
 {
    
public
 int[][] reconstructQueue(int[][] people) {
        
if
 (people.length <= 
1
) {
            
return
 people;
        }

         
         
        binarySort(people, 
0
, people.length - 
1
);
         
        sortByK(people);
         
        
TreeNode
 root = new 
TreeNode
();
        
TreeNode
 temp = new 
TreeNode
();
        temp.val = people[
0
];
        root.next = temp;
        
for
 (int i = 
1
; i < people.length; i++) {
            int[] person = people[i];
             
            
TreeNode
 preNode = root;
            
for
 (int j = 
0
; j < person[
1
]; j++) {
                preNode = preNode.next;
            }
             
            temp = new 
TreeNode
();
            temp.val = person;
            temp.next = preNode.next;
            preNode.next = temp;
        }
         
        int[][] result = new int[people.length][
2 
];
        int index = 
0
;
        root = root.next;
         
        
while
 (root != null) {
            
TreeNode
 node = root;
            result[index] = node.val;
            root = root.next;
            index++;
        }
        
return
 result;
    }

    
public
 void sortByK(int[][] people) {
        int start = 
0
;
        int end = 
1
;
        int[] prePeople = people[
0
];
         
        
while
 (end < people.length) {
             
            
if
 (prePeople[
0
] != people[end][
0
]) {
                
if
 (end - start >= 
2
) {
                    binarySortByK(people, start, end - 
1
);
                }
                prePeople = people[end];
                start = end;
            }
             
            end++;
        }
        
if
 (end - start >= 
2
) {
            binarySortByK(people, start, end - 
1
);
        }
    }

    
public
 void binarySortByK(
            int[][] people,
            int 
left
,
            int 
right
) {
         
        
if
 (
left
 >= 
right
) {
             
return
;
        }
         
        int[] standard = new int[
2
];
        standard[
0
] = people[
left
][
0
];
        standard[
1
] = people[
left
][
1
];
         
        int low = 
left
;
        int high = 
right
;

        
while
 (
left
 
right
) {
             
            
while
 (
left
 
right
 && people[
right
][
1
] >= standard[
1
]) {
                
right
--;
            }
            people[
left
] = people[
right
];
             
            
while
 (
left
 
right
 && people[ 
left
][
1
] < standard[
1
]) {
                
left
++;
            }
            people[
right
] = people[
left
];
        }
         
        people[
right
] = standard;
         
        binarySortByK(people, low, 
right
 - 
1
);
        binarySortByK(people, 
right
 + 
1
, high);
    }

    
public
 void binarySort(
            int[][] people,
            int 
left
,
            int 
right
) {
         
        
if
 (
left
 >= 
right
) {
            
return
;
        }
         
        int[] standard = new int[
2
];
        standard[
0
] = people[
left
][
0
];
        standard[
1
] = people[
left
][
1 
];
         
        int low = 
left
;
        int high = 
right
;

        
while
 (
left
 
right
) {
             
            
while
 (
left
 
right
 && people[
right
][
0
] < standard[
0
]) {
                
right
--;
            }
            people[
left
] = people[
right
];
             
            
while
 (
left
 
right
 && people[
left
][
0
] >= standard[
0
]) {
                
left
++;
            }
            people[
right
] = people[
left
];
        }
         
        people[
right
] = standard;
         
        binarySort(people, low,  
right
 - 
1
);
        binarySort(people, 
right
 + 
1
, high);
    }
}

class
 
TreeNode
 {
    int[] val;
    
TreeNode
 next;
}/<code>

提交OK，但执行时间较长，我们再优化优化。

优化

首先，针对快速排序，是否可以只用一次？答案是肯定的，我们只需要将比较条件特殊处理即可，也就是将上面两次的排序判断条件合并。

其次，针对最终结果的输出，我之前考虑用单向链表，是因为相比于数组每次插入时需要复制，链表的插入比较简单，只需要将地址换掉即可。但链表在找元素过程中耗时较长，数组可以直接利用下标计算出目标位置，且 Java 中的 ArrayList 的 add(int index, E element)，其复制方法是 native 类型，因此效率较高。所以我将最终的结果放入 ArrayList 进行处理。

接下来看看代码：

<code>
 
class
 
Solution
 {
    
public
 
int
[][] reconstructQueue(
int
[][] people) {
        
if
 (people.length <= 
1
) {
            
return
 people;
        }

         
        binarySort(people, 
0
, people.length - 
1
);

        List<
int
[]> 
list
 = 
new
 ArrayList<>(people.length);
         
        
for
 (
int
[] person : people) {
            
int
 k = person[
1
];
            
list
.add(k, person);
        }
         
        
return
 
list
.toArray(
new
 
int
[people.length][
2
]);
    }

    
 
public
 
void
 
binarySort
(
            
int
[][] people,
            
int
 left,
            
int
 right) {
         
        
if
 (left >= right) {
            
return
;
        }
         
        
int
[] standard = 
new
 
int
[
2
];
        standard[
0
] = people[left][
0
];
        standard[
1
] = people[left][
1
];
         
        
int
 low = left;
        
int
 high = right;

        
while
 (left < right) {
             
            
while
 (left < right && !compare(people[right], standard)) {
                right--;
            }
            people[left] = people[right];
             
            
while
 (left < right && compare(people[left], standard)) {
                left++;
            }
            people[right] = people[left];
        }
         
        people[right] = standard;
         
        binarySort(people, low, right - 
1
);
        binarySort(people, right + 
1 
, high);
    }

    
public
 boolean 
compare
(
int
[] person1, 
int
[] person2) {
         
        
int
 height1 = person1[
0
];
        
int
 height2 = person2[
0
];
        
if
 (height1 > height2) {
            
return
 
true
;
        }

        
if
 (height1 < height2) {
            
return
 
false
;
        }

         
        
int
 k1 = person1[
1
];
        
int
 k2 = person2[
1
];
        
return
 k1 < k2;
    }
}/<code>

提交OK，这样速度提升了至少一倍。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要涉及的是找规律和快速排序，优化时需要考虑 Java 中数据结构的特性。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号，说不定会有意外的惊喜。

https://death00.github.io/

關鍵字: while return left