【排序-中等】1366. 通過投票對團隊排名（史上最硬核解析！！！）

【題目】

現在有一個特殊的排名系統，依據參賽團隊在投票人心中的次序進行排名，每個投票者都需要按從高到低的順序對參與排名的所有團隊進行排位

排名規則如下：

參賽團隊的排名次序依照其所獲「排位第一」的票的多少決定。如果存在多個團隊并列的情況，将繼續考慮其「排位第二」的票的數量。以此類推，直到不再存在并列的情況。

如果在考慮完所有投票情況後仍然出現并列現象，則根據團隊字母的字母順序進行排名。

給你一個字元串數組 votes 代表全體投票者給出的排位情況，請你根據上述排名規則對所有參賽團隊進行排名。

請你傳回能表示按排名系統 排序後 的所有團隊排名的字元串。

【示例 1】

輸入：votes = [“ABC”,“ACB”,“ABC”,“ACB”,“ACB”]

輸出：“ACB”

解釋：A 隊獲得五票「排位第一」，沒有其他隊獲得「排位第一」，是以 A 隊排名第一。

B 隊獲得兩票「排位第二」，三票「排位第三」。

C 隊獲得三票「排位第二」，兩票「排位第三」。

由于 C 隊「排位第二」的票數較多，是以 C 隊排第二，B 隊排第三。

【示例 2】

輸入：votes = [“WXYZ”,“XYZW”]

輸出：“XWYZ”

解釋：X 隊在并列僵局打破後成為排名第一的團隊。X 隊和 W 隊的「排位第一」票數一樣，但是 X 隊有一票「排位第二」，而 W 沒有獲得「排位第二」。

【示例 3】

輸入：votes = [“ZMNAGUEDSJYLBOPHRQICWFXTVK”]

輸出：“ZMNAGUEDSJYLBOPHRQICWFXTVK”

解釋：隻有一個投票者，是以排名完全按照他的意願。

【示例 4】

輸入：votes = [“BCA”,“CAB”,“CBA”,“ABC”,“ACB”,“BAC”]

輸出：“ABC”

解釋：

A 隊獲得兩票「排位第一」，兩票「排位第二」，兩票「排位第三」。

B 隊獲得兩票「排位第一」，兩票「排位第二」，兩票「排位第三」。

C 隊獲得兩票「排位第一」，兩票「排位第二」，兩票「排位第三」。

完全并列，是以我們需要按照字母升序排名。

【示例 5】

輸入：votes = [“M”,“M”,“M”,“M”]

輸出：“M”

解釋：隻有 M 隊參賽，是以它排名第一。

【提示】

1 <= votes.length <= 1000

1 <= votes[i].length <= 26

votes[i].length == votes[j].length for 0 <= i, j < votes.length

votes[i][j] 是英文 大寫 字母

votes[i] 中的所有字母都是唯一的

votes[0] 中出現的所有字母 同樣也 出現在 votes[j] 中，其中 1 <= j < votes.length

【代碼】

【Python】

執行用時：

60 ms, 在所有 Python3 送出中擊敗了81.66%的使用者

記憶體消耗：

15.2 MB, 在所有 Python3 送出中擊敗了19.64%的使用者

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        n = len(votes[0])
        # 初始化哈希映射
        ranking = collections.defaultdict(lambda: [0] * n)
        # 周遊統計
        for vote in votes:
            for i, vid in enumerate(vote):
                ranking[vid][i] += 1
        # 取出所有的鍵值對
        result = list(ranking.items())        
        print(result)
        # 排序
        result.sort(key=lambda x: (x[1], -ord(x[0])), reverse=True)
        return "".join([vid for vid, rank in result])
           

【知識點】

collections.defaultdict

在python中使用dict字典的時候，總會遇到一個問題，字典不能直接通路不存在的鍵，不然會抛出KeyError異常，導緻程式中斷。

strings = ('puppy', 'kitten', 'puppy', 'puppy','weasel', 'puppy', 'kitten', 'puppy')
counts = {}
for kw in strings:
    counts[kw] += 1
           

該例子統計strings中某個單詞出現的次數，并在counts字典中作記錄。單詞每出現一次，在counts相對應的鍵所存的值數字加1。但是事實上，運作這段代碼會抛出KeyError異常，出現的時機是每個單詞第一次統計的時候，因為Python的dict中不存在預設值的說法，可以在Python指令行中驗證：

>>> counts = dict()
>>> counts
{}
>>> counts['puppy'] += 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'puppy'
           

如何解決這一問題呢？

在進行對鍵值對操作的時候，首先判斷該key是否存在于該操作的字典之中

【方法1】

這個是我比較習慣的寫法

strings = ('puppy', 'kitten', 'puppy', 'puppy','weasel', 'puppy', 'kitten', 'puppy')
counts = {}
for kw in strings:
	if kw not in counts:
		counts[kw]=0
    counts[kw] += 1
           

【方法2】亦可以這樣寫

strings = ('puppy', 'kitten', 'puppy', 'puppy','weasel', 'puppy', 'kitten', 'puppy')
counts = {}
for kw in strings:
	if kw not in counts:
		counts[kw]=1
	else:
	    counts[kw] += 1
           

【方法3】使用**dict.setdefault()**方法，在對鍵值對操作之前，使用該方法對鍵值指派，當該鍵不存在的時候指派0，否則不進行任何更改操作。

strings = ('puppy', 'kitten', 'puppy', 'puppy','weasel', 'puppy', 'kitten', 'puppy')
counts = {}
for kw in strings:
    counts.setdefault(kw, 0)
    counts[kw] += 1
           

dict.setdefault()方法接收兩個參數，第一個參數是健的名稱，第二個參數是預設值。假如字典中不存在給定的鍵，則傳回參數中提供的預設值；反之，則傳回字典中儲存的值。利用dict.setdefault()方法的傳回值可以重寫for循環中的代碼，使其更簡潔：

strings = ('puppy', 'kitten', 'puppy', 'puppy','weasel', 'puppy', 'kitten', 'puppy')
counts = {}
for kw in strings:
    counts[kw] = counts.setdefault(kw, 0) + 1 
           

【方法4】使用collections.defaultdict類

以上的方法雖然在一定程度上解決了dict中不存在預設值的問題，但是這時候我們會想，有沒有一種字典它本身提供了預設值的功能呢？答案是肯定的，那就是collections.defaultdict。

初始化：

1、使用類型進行初始化，defaultdict類的初始化函數接受一個類型作為參數，當所通路的鍵不存在的時候，可以執行個體化一個值作為預設值：

>>> from collections import defaultdict
>>> dd = defaultdict(list)
>>> dd
defaultdict(<type 'list'>, {})
>>> dd['foo']
[]
>>> dd
defaultdict(<type 'list'>, {'foo': []})
>>> dd['bar'].append('quux')
>>> dd
defaultdict(<type 'list'>, {'foo': [], 'bar': ['quux']})
           

需要注意的是，這種形式的預設值隻有在通過dict[key]或者dict.getitem(key)通路的時候才有效，這其中的原因在下文會介紹。

>>> from collections import defaultdict
>>> dd = defaultdict(list)
>>> 'something' in dd
False
>>> dd.pop('something')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'pop(): dictionary is empty'
>>> dd.get('something')
>>> dd['something']
[]
           

2、defaultdict類除了接受類型名稱作為初始化函數的參數之外，還可以使用任何不帶參數的可調用函數，到時該函數的傳回結果作為預設值，這樣使得預設值的取值更加靈活。下面用一個例子來說明，如何用自定義的不帶參數的函數zero()作為defaultdict類的初始化函數的參數：

>>> from collections import defaultdict
>>> def zero():
...     return 0
...
>>> dd = defaultdict(zero)
>>> dd
defaultdict(<function zero at 0xb7ed2684>, {})
>>> dd['foo']
0
>>> dd
defaultdict(<function zero at 0xb7ed2684>, {'foo': 0})
           

利用collections.defaultdict來解決最初的單詞統計問題，代碼如下：

from collections import defaultdict
strings = ('puppy', 'kitten', 'puppy', 'puppy',
           'weasel', 'puppy', 'kitten', 'puppy')
counts = defaultdict(lambda: 0)  # 使用lambda來定義簡單的函數
for s in strings:
    counts[s] += 1