# Python-LeetCode 581 第八招 Sorting
本單元介紹與Sorting有關的技巧與題目，最重要的是排序的使用方法與時機。通常會用到排序的時機包含：
1. 要將相同的資料放在一起
2. 提高搜尋效率
3. 找前$k$小或是找第$k$小的元素
理論上要找前$k$小或第$k$小的問題，有比排序更好的方法，但其差異不大，在不是太計較的場合之下，排序後來找通常是可以接受的。
此外，很多演算法策略都需要用到排序，例如
* 滑動視窗與雙指針
* 二分搜
* 貪心演算法(Greedy algorithm)
* 動態規劃
這些方法會有另外的單元來專門介紹。
在競賽解題時，參賽者幾乎不需要自己寫排序，而是透過呼叫語言內建的排序函數來完成排序，因為語言內建的排序函數用起來又省事效率又高，所以最重要的是學會使用內建排序函數的使用方法。不過LeetCode與競賽不同，LeetCode也有強制要求自己寫排序的題目。
## Python排序函數的使用方法
Python有兩個排序的函數，list.sort()與sorted(iterable)。
如果將一個list本身排序，我們使用list.sort()；如果我們要得到一個list排序後的結果。如果不希望更改原來的list，可以用sorted(list)。這裡稍微注意list.sort()是不會回傳東西的，而sorted(iterable)是會回傳排序好的list。以下是一些要注意與容易犯錯的地方。
``` python
p = [5,3,1,4]
q = p.sort() # 是錯誤的寫法
q = sorted(p) # 是可以的
# 若要將一個字串的字元排序
s = 'qwerty'
s.sort() # 是錯誤的，因為字串沒有sort函數也無法排序
# 可以寫
q = sorted(s) # 會產生字元排序後的list
>>> q
['e', 'q', 'r', 't', 'w', 'y']
# 也常常這樣用
>>> for c in sorted(s):
print(c, end=',')
e,q,r,t,w,y,
```
這兩個函數的叫用方式十分類似，如果還不熟悉，可以先看看[線上文件](https://docs.python.org/3/howto/sorting.html)。以下我們介紹解題時常用到的使用方法與注意事項。
### 遞增遞減與stable
Python的排序預設是遞增，如果要改成遞減，可以給關鍵字參數reverse=True。例如
```python
>>> p = [3,2,5,1,7]
>>> sorted(p)
[1, 2, 3, 5, 7]
>>> p.sort(reverse=True)
>>> p
[7, 5, 3, 2, 1]
>>>
```
Python的sort是**stable sort**，意思是對於key值相同的元素，排序後不會改變原來的前後關係。例如
```python
>>> p = [(5,7),(2,4),(5,1),(2,8),(5,4)]
>>> sorted(p, key=lambda x:x[0])
[(2, 4), (2, 8), (5, 7), (5, 1), (5, 4)]
>>>
```
此例中p是tuple的list，我們排序時要求key是看tuple的第0個欄位，所以(5,7), (5,1), (5,4)三個的key值是一樣的，所以會保持原來的前後關係。
### 資料的大小關係
Python在資料比較時，有預設的大小關係定義，這是排序的主要依據，其實也用在max/min之類的函數。
1. 數字當然數值小就是小。
2. 字元的關係是以ASCII code的大小來定義，常見的數字字母的ASCII code
'0'<'1'<...<'9' <'A'<'B'...<'Z' < 'a'<'b'...<'z'
3. 兩個字串相比是依據字典順序(lexicographic order)，由前往後找到第一個相異的來比大小。也就是說，第一個先比，如果第一個相同，再比第二個字元，如果第二個也相同就再比第三個字元，...。例如'aaa'<'b'，'aba'<'ac'，'abc'<'abd'。如果比到某個字串全部都結束還是相同，也就是一個字串是另外一個的prefix，那麼，短的比較小。
4. 兩個tuple或兩個list比較時，也是lexicographic order。但個別元素之間必須是可以比較的，數字對數字，字元對字元，字串對字串tuple對tuple，list對list。
### key function
sort()與sorted()內的重要參數是key。前面所說的大小關係是預設的，如果要改變，我們必須透過key這個參數來指定一個函數，做為排序過程中取得key值的依據。舉例來說，我們要排序一些區間，每個區間是(left,right)表示左右端點。如果不指定key，那就是字典序，也就是依照左端點由小到大，左端點相同的會比較右端點。如果我們想用右端點來排序，可以像下面這樣：
```python
>>> def get_right(p):
return p[1]
>>> w = [(3,5),(1, 6),(4,2)]
>>> sorted(w,key=get_right)
[(4, 2), (3, 5), (1, 6)]
>>>
```
像這樣特別定義一個函數來給sort叫用，但在別處並不使用時，會覺得很麻煩，所以通常會使用**無名函數(lambda function)** 的方式，其中Lambda是希臘字母$\lambda$。也就是說，我們只用在此處，所以省略不取名字的函數，做法是在key的地方直接給定義，像下面這樣。
```python
>>> sorted(w, key=lambda x:x[1])
[(4, 2), (3, 5), (1, 6)]
```
lambda x: x[1] 代表傳入的參數如果叫做x，key就取x[1]。
如果我們想用兩個欄位之和來做為key，可以這樣寫
```python
>>> sorted(w, key=lambda x:x[0]+x[1])
[(4, 2), (1, 6), (3, 5)]
```
我們在下面的範例題目中會看到很多排序的例子。另外，在有些狀況下，key function不好定義，而用一個比較函數來做，再透過functools中的cmp_to_key轉成key函數，後面也有個例子介紹使用方式。
以下我們來看一些LeetCode中與排序相關的題目與解法。
## 實作經典排序程序或其一部份
在競賽的場合，通常只要求結果正確與效率夠好，不管你使用的方法，因此碰到需要排序的場合，大多使用現成的排序函數來達成任務。與競賽不同，LeetCode的題目中可能包含要求你實作課本上的經典算法，以下這一題，是個排序的裸題，直接要求實作一個時間複雜度$O(n\log n)$而最小空間複雜度的排序，而不得使用內建的排序函數。
[(題目連結) 912. Sort an Array (Medium)](https://leetcode.com/problems/sort-an-array/)
滿足要求的排序演算法不只一種，最常見的應該是Heap-Sort。這裡我們就以Heap-Sort來示範。
Heap-Sort不難寫，只要先寫好一個往下調整的副程式adj，然後呼叫此函數做初始heapify，接著每一回合把top的最大值與陣列尾端對調並做一次調整。算法細節這裡就不再贅述，不熟悉的讀者，請自行找網路上的教學。
```python=
class Solution:
# heapsort, 0-index, left/right child = 2*i+1, 2i+2
# parent(i) = (i-1)//2
def sortArray(self, nums: List[int]) -> List[int]:
def adj(r,size): # adjust subtree rooted at r
while r+r+1<size:
child = r+r+1
if child+1<size and nums[child+1]>nums[child]:
child += 1
if nums[r]>= nums[child]: return
nums[r],nums[child] = nums[child],nums[r]
r = child
return
#heapify
n = len(nums)
for i in range(n//2-1,-1,-1):
adj(i,n)
# sort
for i in range(n-1,0,-1):
nums[i],nums[0] = nums[0],nums[i] # swap max to tail
adj(0,i) # adjust nums[:i]
return nums
```
下面一題，是搭配串列鏈結來實作Insertion-Sort的裸題，題目中指定了輸入串列的資料結構，也給你Insertion-Sort的步驟。
[(題目連結) 147. Insertion Sort List (Medium)](https://leetcode.com/problems/insertion-sort-list/)
我們用一個dummy node來指著排好序的串列。以指標$p$來歷遍原來的串列，每次將$p$所指的結點放入排好序的串列的正確位置，插入時，以指標$q$來找尋正確的位置。其他的問題是如何在串列中插入與刪除結點，範例程式使用的額外空間是$O(1)$。
```python=
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(-5001,head)
p = head.next
head.next = None
while p: #insert p into sorted list
q = dummy
while q.next and q.next.val<p.val:
q = q.next
tem = p.next
p.next = q.next
q.next = p
p = tem
#endwhile
return dummy.next
```
下面一題是個難度Easy的題目。
[(題目連結) 905. Sort Array By Parity (Easy)](https://leetcode.com/problems/sort-array-by-parity/)
輸入一個整數陣列，要把偶數排在奇數的前面，滿足要求的任意順序皆可。看起來可以用排序來做，key給除以2的餘數即可，以下範例程式中第一行被註解掉的就是這樣的解。
但事實上這題有更好的方法。因為只有偶數與奇數兩類，要把東西分成左右兩類，我們可以這樣做：由前往後找第一個奇數，由後往前找碰到的第一個偶數(也就是最後一個偶數)，交換兩者。
由剛才的位置(不必從頭)繼續這個尋找與交換的動作，直到第一個奇數在最後一個偶數之後為止。其實這個程序就是quick-sort中每次將數字切割為比pivot小與比pivot大兩類時常用的程序寫法，時間複雜度是$O(n)$。這個方法適用於將序列中分成前後兩類的狀況。
```python=
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
# return sorted(nums, key=lambda x: x&1)
i,j=0,len(nums)-1
while i<j:
while i<j and nums[i]&1==0:
i += 1
while i<j and nums[j]&1: j -= 1
if i<j: nums[i],nums[j] = nums[j],nums[i]
return nums
```
## 以排序來達成目標
題目中直接要求完成某種排序，或者直接與排序相關的任務。以下依照排序的對象類別，分類舉例說明。
### 數字或字元排序
在下面這題裡，要對一個二維矩陣的每一條對角線進行排序。
[(題目連結) 1329. Sort the Matrix Diagonally (Medium)](https://leetcode.com/problems/sort-the-matrix-diagonally/)
重點是正確的抓出每一條對角線，然後呼叫排序後再塞回對角線就可以了。
```python=
class Solution:
def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
m,n = len(mat),len(mat[0])
for i in range(m-1):
tem = sorted([mat[i+j][j] for j in range(min(n,m-i))])
for j,k in enumerate(tem):
mat[i+j][j] = k
for j in range(1,n-1):
tem = sorted([mat[i][j+i] for i in range(min(m,n-j))])
for i,k in enumerate(tem):
mat[i][i+j] = k
return mat
```
下面這題中，給你若干加熱器的位置(一維)以及若干房子的位置，請計算最小的加熱器的半徑，使得每一間房子都至少在一台加熱器的半徑範圍內。
[(題目連結) 475. Heaters (Medium)](https://leetcode.com/problems/heaters/)
對每一間房子，找出其左右最近一台加熱器的距離，然後對所有房子取此距離的最大值就是答案。也就是
$$
\max_{h\in \text{house}}\{\min_{i \in \text{heater}} |h-i|\}
$$
我們可以對所有加熱器先做好排序，每一間房子可以快速的用二分搜找到他左右最近加熱器的位置。
連續的二分搜可以一路爬過去，所以將房子也排序後，用雙指針的方式爬過去就可以找出答案了。
這是排序後雙指針或二分搜的題目。時間複雜度$O(n\log n+m\log m)$，$m,n$是加熱器與房子的數量。下面的程式中，我們在加熱器的頭尾加了極小與極大的位置，來減少邊界檢查的動作，是個常用的sentinel小技巧。
```python=
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
heaters = [-2e9] + heaters + [3e9]
i = 1
radius = 0
for h in houses: # h always in (heaters[i-1],heaters[i]]
while heaters[i]< h:
i += 1
r = min(heaters[i] - h, h-heaters[i-1])
if r> radius: radius = r
return radius
```
下面是字串題。
[(題目連結) 49. Group Anagrams (Medium)](https://leetcode.com/problems/group-anagrams/description/)
Anagram是指把一個字串中的字母重排後的字串，也就是兩個字串所有的字母，以及每個字母出現次數，都完全相同。本題要求在一群字串中，把屬於同一組的anagram放在一起。
這屬於一個分類的問題。在分類問題中，我們可以訂出每一個分類的代表值(或特徵值)，也就是同一類的物品此代表值皆相同，而不同類的皆不相同。然後計算每一個物品的代表值之後就可以歸屬到他所屬的類別。
根據題意，本題有一種定義代表值的方法是每個字母的出現次數，那麼就會是一個26個整數的tuple。
另外一個方法就是將字串內的字母排序後當作代表值，因為顯然每一個anagram的字母排序後是一樣的。
我們用defaultdict(list)來蒐集每一個類別，對每一個字串$s$，用sorted($s$)會得到字母排序後的list，python的list是不可以當作dict的key，因此我們用字串函數''.join(sorted($s$))把他轉成字串後當作key。
最後，要輸出答案時，每一群anagram都在一個字典值(是一個list)中，我們用d.values()可以取出所有的字典值。也可以寫return list(d.values())，d.values()雖然不是一個list，但可以自動轉換為list。
```python=
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
d[''.join(sorted(s))].append(s)
return d.values()
```
下面這一題也是字串題，要求依照字串內字元出現的次數由多到少將字元重新排列，字元包含大寫與小寫字母。例如輸入"tree"，要輸出"eert"或"eetr"，也就是相同次數時，哪個字母在前都可以。
[(題目連結) 451. Sort Characters By Frequency (Medium)](https://leetcode.com/problems/sort-characters-by-frequency/)
我們先要將字元出現的次數計算出來，然後由多到少排出字母的順序，最後建構出輸出的字串。計算字母出現次數，可以用表格，因為本題有大小寫，用字典更簡單一些。以下是用基本字典來計算次數的一個範例程式。
```python=
class Solution:
def frequencySort(self, s: str) -> str:
d={}
for c in s:
if c in d: d[c] += 1
else: d[c] = 1
icount = []
for c in d:
icount.append((d[c], c))
icount.sort(reverse=True)
ans = ""
for t,c in icount:
ans += c*t
return ans
```
使用python的基本字典，要小心踩到KeyError，如果c不在d中，寫d[c]+=1就會出問題。所以程式的第5 ~ 6行需要用if來寫。計算次數完畢後，我們將每一個出現次數與字元組成一個tuple放入一個list icount中排序，要用來比較的次數放在前面，reverse=True會排反序(大到小)，最後輸出時，我們利用字串的乘法(重複)與加法(串接)可以很容易的建構出要的字串。
利用字典的一些功能可以簡化程式，以下是利用 Counter的寫法。Counter是對應值為數字的一種字典，用來統計次數特別好用，他有個功能most_common會產生次數由多到少的(key,value)的tuple，most_common($k$)會產生前$k$大，不給參數就是全部。我們直接用迴圈歷遍這些tuple並建構出輸出字串，程式變得十分簡潔。
```python=
class Solution:
def frequencySort(self, s: str) -> str:
ans = ""
for c,i in Counter(s).most_common():
ans += c*i
return ans
```
下面這個題目是說給你一個數字，有沒有辦法把他的每一個位數重新排列後得到一個2的冪次的數字。例如輸入如果是2014，我們可以透過重排後得到1024=$2^{10}$。重排後的數字要求不得有leading zero。
[(題目連結) 869. Reordered Power of 2 (Medium)](https://leetcode.com/problems/reordered-power-of-2/)
乍看之下有點麻煩，輸入的數字每個位數拆開後，我們要嘗試所有可能的排列，然後檢查是否是2的冪次。其中最麻煩的是「嘗試所有排列」。雖然這題的數字的位數最多只有10位，不會太大，但這樣做還是耗時而麻煩。
解題時，有時是順向思考，根據題意去建構去檢查；有時候可以逆向思考：**從可能的解答下手**。這題可能的2的冪次只有30個：$2^0, 2^1, \ldots, 2^{29}$，那排列怎麼辦呢？就像前面anagram那題講分類的手法，我們把重新排列的當作是同一類，每一類的代表型就是把各個位數由小到大排列的「字串」。對於輸入的數字，建出代表型查查看他是否在裡面就知道答案了。以下是範例程式。
```python=
myset = set()
for i in range(30):
myset.add("".join(sorted(str(1<<i))))
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
return "".join(sorted(str(n))) in myset
```
### 區間與平面座標
區間$[left,right]$是指一段連續的數字的集合，在程式題中常專指整數。平面座標是一對數字$(x,y)$。兩者都是有一對數字的題目，是程式題中常出現的資料形式。
下面這一題是有關平面座標的排序。
[(題目連結) 973. K Closest Points to Origin (Medium)](https://leetcode.com/problems/k-closest-points-to-origin/)
平面上有若干點，找出離原點最近的$k$個點，輸出任意順序。我們只要將點依照離原點的距離排序就可以了。
座標$(x,y)$的點離原點的距離為$\sqrt{x^2+y^2}$，因為開根號是遞增函數，也就是若$p>q\geq 1$，$\sqrt{p}>\sqrt{q}\geq 1$。所以我們依照沒開根號之前的值來排序就可以了，排序之後就回傳前$k$個的list。
```python=
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
points.sort(key=lambda p: p[0]*p[0]+p[1]*p[1])
return points[:k]
```
線段或區間(interval)的題目也非常多，大部分會歸類到Greedy或DP。
下面這一題要求將區間做聯集，也就是有重疊的要合併成一個區間。
[(題目連結) 56. Merge Intervals (Medium)](https://leetcode.com/problems/merge-intervals/)
我們的重點是要避免重複的檢查。
將輸入線段依照左端排序後，從第一根線段開始，我們始終會保持著目前最後一根線段$[le,ri]$，在檢視下一根線段$[s,t]$時：
1. 如果$s>ri$，也就是$[s,t]$與$[le,ri]$沒有交集，那麼後面的所有線段都不會跟$[le,ri]$有交集，因為是左端排序，後面的左端越來越大。這時，我們將$[le,ri]$納入輸出中，從此再也不用管他。然後，將$[s,t]$當作目前的最後一段。
2. 否則，$[s,t]$與$[le,ri]$有交集，我們需要把$[s,t]$併入$[le,ri]$，要做的事情是對右端取較大者，因為$le\leq s$。
以下是範例程式，時間複雜度是$O(n\log n)$，排序加上一次線性掃描。
```python=
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
out = []
intervals.sort()
le,ri = intervals[0]
for s,t in intervals:
if s > ri:
out.append([le,ri])
le,ri = s,t
else :
ri = max(ri,t)
out.append([le,ri])
return out
```
下面這一題也是區間線段的經典問題。
[(題目連結) 435. Non-overlapping Intervals (Medium)](https://leetcode.com/problems/non-overlapping-intervals/)
給一些線段，請移除最少的線段使得剩下的線段均無重疊。換句話說，要找這些線段的一個彼此不相交的最大子集，以圖論的術語來說，這一題就是max independent set on interval graph。
這題有另外一個名稱：activity selection problem。故事是這樣說的，有一些活動想要參加，第$i$個活動的時間是$[s_i, t_i]$，每參加一個活動必須從頭到尾不遲到不早退，同一個時間不能參加兩個活動，請問最多可以參加幾個活動。
我們來說說算法，它是一個貪心的策略。
將區間以右端排序，挑選結束時間最早的區間，也就是最早結束的活動。與已挑選區間重疊的區間就放棄，重複挑選剩下活動中最早結束的，直到所有活動挑選完畢。
貪心算法的證明都是類似的：證明每一個決策是正確的。在本題中，我們可以證明：一定有一個最佳解跟我們所挑選的活動一樣。假設我們所挑選的最早結束的活動是$[x,y]$，而最佳解沒有挑選此活動。假設最佳解挑選的活動中最早結束的是$[s,t]$，那麼我們宣稱將最佳解中的$[s,t]$替換為$[x,y]$依舊是一個合法的解而且活動數不減。
因$[s,t]$是最佳解中最早結束的活動，最佳解中其他的活動$[p,q]$不可能與$[s,t]$有交集，因此，開始時間必定$p> t$。根據假設，$[x,y]$是最早結束的活動，也就是$y\leq t$，因此$p>y$，$[p,q]$與$[x,y]$無交集。
設計程式時，我們不須在區間中挑選最小右端。我們將區間依照右端排序後，做一次歷遍，最早碰到的就是最小右端。紀錄已挑選活動的最後一個右端last，碰到的區間如果左端$\leq$last，就表示與挑選區間有重疊，應放棄；如果左端>last，就表示是下一個最小右端的活動，應該挑選起來。程式寫起來很簡潔。以下是範例程式，時間複雜度是$O(n\log n)$，排序加上一次歷遍。
```python=
class Solution:
# activity selection problem
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1]) # sort by right
total = 0
last = -50001 # initial -oo
for s,t in intervals:
if s>= last:
total += 1
last = t
return len(intervals)-total
```
這一題是要求須要移除的，最後回傳所有的區間數減去最多不相交區間才是答案。
這題還有另外一個面目，但兩者的等價也許不是那麼容易直覺。如果選擇一個點$x$可以戳中所有包含$x$的區間，請問最少要選擇幾點才能戳中所有的區間。圖論的術語是min clique partition。不難證明上面的算法也可以求得min clique partition的最佳解，也就證明了兩者的等價，
### 結構資料排序
[(題目連結) 1090. Largest Values From Labels (Medium)](https://leetcode.com/problems/largest-values-from-labels/)
題目是說有$n$個物品，每個物品有value(非負整數)與label，從中要挑選最多不超過$numWanted$個，希望價值總和最大，但同一種label不得超過$useLimit$個。
這也是個貪心策略的題目，依照價值由大到小，同一種標籤紀錄已挑選個數。
以下是範例程式，我們用Counter來計數，排序時將value與label用zip組成tuple一起排序，value在前，以便依照value排序。同一類超過限制就跳過(第7行)，數量取滿就直接離開，否則跑到迴圈結束。
```python=
class Solution:
def largestValsFromLabels(self, values: List[int], labels: List[int], numWanted: int, useLimit: int) -> int:
n = len(values)
cnt = Counter()
score,i = 0,0
for v,l in sorted(zip(values,labels), reverse=True):
if cnt[l] >= useLimit: continue
score += v
cnt[l] += 1
i += 1
if i==numWanted: break
return score
```
不熟悉的讀者請了解sorted(zip())的寫法。zip(拉鏈)是python中一個好用也常用的工具。若$p,q$兩個list，zip(p,q)會像拉鏈一樣組成((p[0], q[0]), (p[1], q[1]), ...,)，長度會以短的那個為準。zip也可以組合多個list。例如在二維陣列中取出行向量(或轉置矩陣)也很好用。下面的例子，第2行的寫法立刻可以得到行向量的list，但這樣寫每一個行向量都是tuple不是list，如要轉成list可以像第3行那樣寫。請留意tuple是immutable，不允許修改其成員。
```python=
mat = [[1,2,3],[4,5,6]]
q = list(zip(*mat)) # [(1, 4), (2, 5), (3, 6)]
qq = list(list(col) for col in zip(*mat))
# [[1, 4], [2, 5], [3, 6]]
```
下面這題乍看之下可能不知道要如何下手。
[(題目連結) 1296. Divide Array in Sets of K Consecutive Numbers (Medium)](https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/)
題目是給一個整數序列以及一個正整數$k$，請問序列可否被**完美的切割為長度$k$的連續整數區間**，例如$nums = [1,2,3,3,4,4,5,6]$而 $k = 4$，則可以完美切割為兩個長度4的連續整數區間$[1,2,3,4]$與 $[3,4,5,6]$。完美切割是指不能有剩下的，也不可重複使用。
這題有點像在一堆亂七八糟的線中要抽出一條一條的線。如果序列中的最小值是$p$，那他一定是一個區間的第一個數，如果答案是可以切割，必然有一個區間是$[p,p+1,\ldots,p+k-1]$，我們可以把他當一個線頭，把這條線一步一步抽出來。然後再繼續找下一個線頭，過程中如果失敗，答案就是無法切割。
為了順利的找到區間的下一個元素，我們需要做一些處理，單純的排序並不符合我們的要求，因為排序後$q$的下一個不一定是$q+1$，可能是另外一組的$q$。所以我們把相同的數字搜集起來再排序，每個數字紀錄他出現多少次。
以下是範例程式，在第4行我們用Counter搜集每個數字出現的次數，然後將$(p, p的次數)$這樣的資料依照數字排序。為了方便起見，我們由後往前做，也就是由大往小去找。進入迴圈後先把最後，也就是最大的數字$p$ pop出來，出現次數是np。從list的尾端刪除元素的時間是$O(1)$，這是我們由後往前做的原因。
如果次數np=0，則進行下一回合(找另外一個線頭)，否則開始抓出這np條相同線頭的線。第8行檢查是否還有足夠多的數字，第9行，我們往前找連續的$k-1$組數字，每個都需要有np個以上。
時間複雜度：$O(n+m\log m)$，排序加上線性掃描，$n$是序列長度，$m$是不同數字的個數。留意到雖然有雙迴圈，但是每看過一個數字會把它拿掉，因此第9行的for迴圈對同個數字的操作並不會超過該數字的出現次數。
這題要從前往後做也是可以的。
```python=
class Solution:
def isPossibleDivide(self, nums: List[int], k: int) -> bool:
if len(nums)%k: return False
seq = sorted([[x,y] for x,y in Counter(nums).items()]) # [p, num of p]
while seq:
p,np = seq.pop()
if np==0: continue
if len(seq) < k-1: return False
for i in range(-1,-k,-1):
if seq[i][0] != p+i or seq[i][1] < np: return False
seq[i][1] -= np
return True
```
### 特殊排序
[(題目連結) 1921. Eliminate Maximum Number of Monsters (Medium)](https://leetcode.com/problems/eliminate-maximum-number-of-monsters/)
題目是說$n$隻怪獸進攻你的城市，第$i$隻怪獸距離為$dist[i]$，以速度$speed[i]$等速近逼。你的武器每分鐘可以消滅一隻怪獸，請問在怪獸進攻到城市之前，最多可以消滅多少隻，或者全部消滅。
重點在於先算出每隻怪獸的到達時間，依照到達時間排序，先到達的怪獸要先消滅。
下面範例程式中，我們在第3行算出到達時間並排序，因為要的是整數除法無條件進位，所以用$(p-1)//q+1$。排序後一一檢查，前$i$隻如果有時間$\leq i$的話，城市就被攻陷了。
```python=
class Solution:
def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
s = sorted([(p-1)//q+1 for p,q in zip(dist,speed)])
for i,t in enumerate(s):
if t<=i: return i
return len(s)
```
[(題目連結) 179. Largest Number (Medium)](https://leetcode.com/problems/largest-number/)
給你一些非負整數，你要把這些數字像字串一樣接起來，變成一個很大的數字，產生的數字越大越好。
當然，最前面的那一位數字最重要，我們會先找9開頭的，然後8開頭的，...。同樣是9開頭的之中，要比較第二位，看起來把數字當成字串來比較就對了。例如$\{ 1, 20, 96, 92, 532\}$，我們就排成9692532201。這個方法在範例二遇到問題，輸入是$nums = [3,30,34,5,9]$，前面沒問題先排95，後面三個都是3開頭，如果照字串的方式排是34303，但應該要排34330比較大。
其實長度一樣的時候照字串的方式比大小是對的，但長度不一樣的時候，就不對了。以字串來說明，若一個數字是某個數字的前綴，也就是$p$與$pq$，必須看$ppq$比較大還是$pqp$比較大，也就是$q$跟$p$哪一個大。例如3與30，0<3，所以330比較大，如果是3與34，就要擺成343。比較直覺的就是不管前綴，把兩個數字前後放放看，哪個順序大就取哪個。
這個順序顯然還是滿足遞移性的，所以可以拿來排序。因此我們要把這些數字排序，而排序的依據是
**對於字串$p$與$q$，$p$排在$q$之前，若且惟若$pq > qp$。**
要如何用Python完成這樣的排序呢？
這種我們稱為compare function，在C/C++的內建排序函數都允許使用自訂的比較函數，Python在版本2的時候也允許，但在Python 3之後，取消了這個使用方法，只能使用自訂key。但是functools裡面提供了一個轉換方式，cmp_to_key(cmp_func)，可以將自訂的比較函數轉換成key。
以下是範例程式。先寫一個比較函數cmp，輸入兩個字串$s1$與$s2$，如果第一個參數要排序在前面就回傳負整數，否則回傳正整數。
第6行我們將輸入的整數轉換成字串，第7行呼叫排序，最後，我們把排序後的字串依序接起來。第11行是避免輸入是類似$\{0,0\}$這種情形。
```python=
class Solution:
def largestNumber(self, nums: List[int]) -> str:
def cmp(s1,s2):
if s1+s2 > s2+s1: return -1
return 1
s = [str(x) for x in nums]
s.sort(key=cmp_to_key(cmp))
ans = ""
for x in s:
ans += x
if ans[0]=='0': return '0'
return ans
```
如果寫短一點可以寫成
```python=
class Solution:
def largestNumber(self, nums: List[int]) -> str:
def cmp(s1,s2):
if s1+s2 > s2+s1: return -1
return 1
ans = "".join(sorted([str(x) for x in nums], \
key=cmp_to_key(cmp)))
if ans[0]=='0': return '0'
return ans
```
這題還有一種給key值的方式，就是將短的字串多重覆幾次到分的出大小為止。因為原始輸入的數字長度不超過10，我們就重覆到至少10位。以下是範例程式，字串乘以一個整數是重覆該字串若干次。
```python=
class Solution:
def largestNumber(self, nums: List[int]) -> str:
s = [str(x) for x in nums]
s.sort(key=lambda x: x*(9//len(x)+1),reverse=True)
ans = ""
for x in s:
ans += x
if ans[0]=='0': return '0'
return ans
```
下面這一題是要依照指定的順序來排序。
[(題目連結) 791. Custom Sort String (Medium)](https://leetcode.com/problems/custom-sort-string/)
給兩個字串，$order$與$s$，要把$s$內的字元重新排列，字元排列的依據是：字元在$order$中的順序。要留意，字元可能沒有出現在$order$中，此時放在哪裡都沒有違反要求。
重點就是定義出一個key function可以對應給order中的順序。所以我們可以用一個字典來做這件事，把字元出現在$order$中的順序存成字典的對應值。為了沒有出現的字元，我們一開始把所有字元的對應值都給26(最大)。歷遍一次$order$給出現字元順序，然後呼叫排序，最後串接排序後的字元。
```python=
class Solution:
def customSortString(self, order: str, s: str) -> str:
d = {chr(0x61+i):26 for i in range(26)}
for i,c in enumerate(order):
d[c] = i
w = sorted(s, key=lambda x: d[x])
return "".join(w)
```
## 排序有關的問題
以下的題目是跟排序有關的問題，但並非是需要做排序的問題。
[(題目連結) 581. Shortest Unsorted Continuous Subarray (Medium)](https://leetcode.com/problems/shortest-unsorted-continuous-subarray/)
題目是說有一個整數陣列，請找出最短的連續一段區間，滿足：將此段排序後，整個陣列都會是排好序的。
最壞的情形就是整個數列都要排，所以一定找得出答案。觀察一下，如果最小值出現在第$i$個，那麼$i$以前的都必須被納入；如果最小值出現在最前面($i=0$)，那麼最前面這個就不必納入。所以我們要找出前面最長一段是已經排在正確位置的，相同的，找出後面最長的一段是已經在正確位置的，中間這一段就是答案。
如何找出前面已經在正確位置的最長一段呢？如果所有的元素皆相異，我們可以排序一次找出所有元素應該在的位置(rank)。但本題可能有相同元素，單純用rank可能有麻煩。我們可以觀察到以下特性：
* 對於任何一個元素，**假如他的後方沒有比他小的，他就是在正確的位置**。我們要找的是一個前綴，前綴中全部都在正確位置，
* 所以我們找第一個不在正確位置的，就是所求區間的左端。相同的，找最後一個不在正確位置的，就是右端。
要找出第一個後方有更小值的位置$le$，我們由後往前掃，記錄著目前看到的最小值(suffix min)，如果$nums[i]$大於他的後綴最小值，就更新$le=i$，最後一個被更新的就是要找的左端。找右端的方法是一樣的。
以下是範例程式，時間複雜度$O(n)$。
```python=
class Solution:
'''
Let the solution be [left,right]. Then,
left is the smallest index with smaller on its right.
right is last index with larger on it left side.
'''
def findUnsortedSubarray(self, nums: List[int]) -> int:
n = len(nums)
le,ri = n,-1
pmax = -100001
for i,v in enumerate(nums):
if v<pmax: ri = i
if v>pmax: pmax = v
smin = 100001
for i in range(n-1,-1,-1):
if nums[i]> smin: le = i
if nums[i] < smin: smin = nums[i]
if le<ri: return ri-le+1
return 0
```
下面這一題難度是Hard。
[(題目連結) 220. Contains Duplicate III (Hard)](https://leetcode.com/problems/contains-duplicate-iii/description/)
給一個整數陣列，以及兩個**限制**，請問是否存在兩個元素，位置差距與數值差距都在給定的限制之內。
觀察一下退化的情形，假如數值差距的限制是0，也就是找位置限制下是否有相同元素。這個題目就不難了，我們可以用滑動視窗，用一個字典紀錄視窗範圍內出現的數字與次數，視窗每移動一步時，在字典減少移出數字的次數，查詢新進來的元素是否在字典中出現。
現在數值差距限制不一定是0。這個跟一種排序方法bucket sort是類似的情境。我們可以把數值的範圍切割成一些區間，區間的大小就定義為bsize=valueDiff+1，其中valueDiff是給定的數值差距限制。對於每一個數字$x$，我們把他丟進編號$x//bsize$的桶子裡。如果距離範圍內有兩個元素進到同一個桶子，則他們的差值必然不超過要求的差距。這還不足夠，我們還需要檢查隔壁的桶子，因為兩個相鄰的桶子有可能有差距範圍內的數字。
以下是範例程式。題目給的範圍是從$-10^9$開始，所以計算桶子編號時，我們把每個數字加上$10^9$平移到非負整數。
```python=
# bucket of size valueDiff+1, dict
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
d = {}
bsize = valueDiff+1
for i,x in enumerate(nums):
if i>indexDiff: # remove
d.pop((nums[i-indexDiff-1]+10**9)//bsize)
bucket = (x+10**9)//bsize
if bucket in d: return True
if bucket-1 in d and d[bucket-1]>=x-valueDiff:
return True
if bucket+1 in d and d[bucket+1]<=x+valueDiff:
return True
d[bucket] = x
return False
```
下面這一題其實有一些故事可以說。
[(題目連結) 969. Pancake Sorting (Medium)](https://leetcode.com/problems/pancake-sorting/)
題目是說有$n$個大小為$1,2,\ldots,n$的煎餅以打亂的順序上下堆在一堆，我們想要把他們由上到下排列成由小到大，但是只能使用以下的操作(Prefix reversal)：
選擇一個位置$k$，將最上方的$k$個煎餅順序反轉。
題目並不要求最小的次數，只要在$10n$次以內皆算通過，要輸出每次選擇的位置$k$。
因為每次翻轉都是翻轉prefix，假設最大的已經在最後一個時，我們只要解剩下$n-1$個的問題就可以了。從遞迴化簡問題的角度，很容易想出一個可行的解：
找出最大的煎餅所在位置$j$，將前$j$個反轉，把最大的翻到最上方，然後再翻轉全部，將最大的翻到最下面。遞迴解剩下的$n-1$個。
因為翻兩次可以減少一個，排序$n$個所需要的次數可以表達為$T(n)\leq T(n-1)+2$ for $n>2$; and $T(2)\leq 1$，$T(1)=0$。所以$T(n)\leq 2n-3$。比題目要求的$10n$要好很多。
撰寫程式時不必寫遞迴，我們跑一個迴圈從$n$到1，每次找到$i$的位置，紀錄並模擬翻轉的動作即可，時間複雜度$O(n^2)$。list的反轉用Python很好寫，以下是範例程式。留意Python允許等號左邊也是一段list，他會取代對應的部分，這樣不必一個元素一個元素的指定。
```python=
class Solution:
def pancakeSort(self, arr: List[int]) -> List[int]:
flip = []
for i in range(len(arr),0,-1):
j = arr.index(i)
if j == i-1: continue
flip += [j+1,i]
arr[:j+1] = arr[j::-1]
arr[:i] = arr[i-1::-1]
return flip
```
Pancake問題的最小翻轉次數是多少呢？很抱歉，目前沒有有效率的解法，他其實是個很複雜的問題，本題只要求一個近似解就可以了。這個問題之所以有名，是因為微軟的創辦人Bill Gates在當念大學時，做了一個此問題的研究，並將論文發表在一個高水準的學術期刊，他的共同作者是計算理論很著名的學者。小學老師只告訴你Bill Gates大學沒念畢業就創辦微軟的勵志故事，但可能沒告訴你，他大學沒畢業就已經有很強的研究能力。想要了解此問題可以查[網路](https://en.wikipedia.org/wiki/Pancake_sorting)。
## 組合技
下面這一題有結合一些其他的技巧。
[(題目連結) 1383. Maximum Performance of a Team (Hard)](https://leetcode.com/problems/maximum-performance-of-a-team/)
題目是說有$n$個工程師，第$i$位的速度是$speed[i]$，效率是$efficiency[i]$。現在要從中挑選最多$k$位，希望**績效**最佳。績效的計算方式是：**(所挑選人的速度總和)乘以(所挑選人中的最低效率)**。
兩個變數不容易掌握，我們嘗試固定其中一個。效率是取最小值，假設我們所取到的最小效率值是$e$，效率$\geq e$的工程師怎麼選，最終的效率都是$e$，要最大化績效就等同於最大化**速度之和**，因此，應該要選取速度最大的$k$位工程師。
結論是，對於每一個可能的效率值$e$，尋找效率$\geq e$而速度最大的工程師至多$k$位。
因為對於每一個可能的$e$都需要計算，為了避免重覆計算，我們讓$e$值由大到小逐步降低，留住目前速度最大的$k$位，每次降低$e$的值，納入更多可能的速度，放棄速度第$k$名之後的工程師。
以下是範例程式。一開始先將效率與速度依照效率由大排到小(第4行)，為了保持目前速度最快的$k$位工程師，我們使用一個min-heap(第5行)。ssum將會記錄在pq中最大$k$個的速度之和(我們要避免每次重算)。第8行開始歷遍，每次將下一個效率值的速度$s$放入pq，先將$s$加入ssum，如果pq已超過$k$個，我們把最小值pop出來，並從ssum中扣除。對於每個$e$都計算一次目前最佳值(第12行)。
```python=
class Solution:
# sweep from large to small efficiency, keeping the max k speed
def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
seq = sorted(zip(efficiency,speed),reverse=True)
pq = [] # max k speed
ssum = 0 # sum of max k speed
opt = 0
for e,s in seq: # current min efficiency
heappush(pq,s)
ssum += s
if len(pq)>k: ssum -= heappop(pq)
opt = max(opt,ssum*e)
return opt%1000000007
```
也可以把效率與速度看成平面的$X$與$Y$座標，要選取最多$k$個點。以掃描線的觀念，用一條垂直線由左往右掃過去，掃瞄線左方的點用一個heap紀錄$Y$值最大的$k$個點。
[(題目連結) 2007. Find Original Array From Doubled Array (Medium)](https://leetcode.com/problems/find-original-array-from-doubled-array/)
題目說有一個原始整數陣列，有人將原始陣列的每一個元素的兩倍值加入陣列中，然後將陣列順序打亂後得到一個陣列。輸入這個加工後的陣列，我們要算出原始的陣列，或者決定此陣列不存在，也就是所給的陣列並非如此建構出來的。陣列數字範圍為$[0,10^5]$，是非負整數。
因為是非負整數，我們可以從最小值下手，在正整數的情況下，**最小值一定是原始陣列的元素**，在最小值是0的狀況下，一定有一個0是原陣列元素。
我們把找到的一個最小值$p$紀錄為原陣列元素後，就可以標記一個$2p$為非原陣列元素，如果找不到$2p$，那就是失敗。然後我們可以重覆上述程序，再找下一個最小值。
為了效率起見，我們排序後從小到大歷遍，為了快速找到$2p$，我們可以用二分搜，但是因為要一路二分搜，不如另外用一個指針往右滑動。此外，要記錄哪些已知是原陣列的2倍而非原陣列元素，我們使用一個List dead，dead[$i$]=True表示第$i$個並非原陣列元素。
以下是範例程式。一開始第3行先排序。用$i$歷遍，$j$用來找$2p$，因為$i$遞增，所以$j$只要上升來尋找。開始歷遍時，如果遇到的是非原陣列元素，跳過換下一個。然後移動$j$找到第$i$個的兩倍，而且必須是還存在的元素(dead[j]==False)。如果找不到值就結束並回傳空list。找到的話，將第$i$個放入答案，而將第$j$個標記為dead。
時間複雜度$O(n\log n)$，排序加上歷遍。
```python=
class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
changed.sort()
n = len(changed)
dead = [False]*n
ans = []
j = 1
for i in range(n):
if dead[i]: continue
dead[i] = True
while j<n and (dead[j] or changed[j]<changed[i]+changed[i]):
j += 1
if j==n or changed[j]!=changed[i]+changed[i]:
return []
dead[j] = True
ans.append(changed[i])
return ans
```
## 結語
排序本身、排序的運用以及與排序有關的問題，都有非常多資料結構與演算法的問題，在歷史的發展上，也是如此。
需要用到排序的算法也非常多，特別是在Greedy、DP以及與序列相關的問題，這些會有單元專門介紹。
Sign in with Wallet
Connect another wallet