這道題主要涉及的是找規律和快速排序，優化時需要考慮 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 = newTreeNode
();TreeNode
temp = newTreeNode
(); 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 = newTreeNode
(); 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, intleft
, intright
) {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, intleft
, intright
) {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
booleancompare
(
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/
