我已經解決了 leetcode 1366，但是在近似正確的時間/空間復雜度時遇到了一些麻煩。我查看了解決方案選項卡，但答案各不相同，我不確定我是否購買其中一些。這是我的代碼和一般演算法 -
class Solution:
def rankTeams(self, votes: List[str]) -> str:
rankings = {}
team_count = len(votes[0])
for vote in votes:
for position, team in enumerate(vote):
if team not in rankings:
rankings[team] = [0 for _ in range(team_count)]
rankings[team][position] = 1
alphabetically_ordered_teams = sorted(rankings.keys())
final_ranking = sorted(alphabetically_ordered_teams, key = lambda team : rankings[team], reverse=True)
return ''.join(final_ranking)
演算法：
遍歷團隊陣列并構建一個哈希圖，其中每個團隊映射到一個陣列，其中 array[i] 是他們在該位置收到的票數
例如，對于 case ["ABC"]，地圖將如下所示：
{
A: [1, 0, 0]
B: [0, 1, 0]
C: [0, 0, 1]
}
按字母順序對 hashmap 的鍵進行排序。如["A", "B", "C"]
使用我們之前構建的 hashmap 中每個元素的值對這個按字母順序排列的串列進行排序。這樣我們比較它們的值，這是每個位置的投票陣列，如果有平局，那么我們可以依靠字母順序來獲得我們想要的順序。我們反向排序，因為結果應該是降序的。
我認為時間和空間復雜度應該分別為 O(N) 和 O(1)，但我不確定。
遍歷字串陣列將是 O(N * 26)，因為 votes[i] 的約束狀態是 <= 26，這是小寫字母 a->z 的數量。即使我們允許更多字符，它也將始終保持不變，因為 unicode 字符的數量是不變的。
對 hashmap 的鍵進行排序在時間和空間上都是 O(1) 操作，因為只能有 26 個鍵。
最后的排序操作：我認為 hashmap 值中的元素數等于給定投票可以具有的字符數。所以對于"ABC"，陣列中只有 3 個元素對應于每個位置的 3 個投票，例如 ' [0, 0, 0']。因此，我認為排序也將是一個恒定的時間/空間操作。
我認為作為排序鍵的 lambda 函式必須比較被排序的兩個值陣列的元素。那是 O(N)^2 嗎？我猜在這種情況下 O(26)^2 ？或總體上為 O(1)。
因此，我的整體時間復雜度類似于 O((N * 26) 26log26 * 26^2) => O(N) 和空間復雜度 O(1)。
這是錯的嗎？
uj5u.com熱心網友回復：
當您確定實際代碼使用的時間或空間的漸近復雜度時，您決定將哪些值視為變數或常量。在這種情況下，如果您根據 leetcode 問題的約束做出此決定
1 <= votes.length <= 1000
1 <= votes[i].length <= 26
那么可能的資料大小完全受常數限制，因此在這種形式化下，運行時間為 O(1)，但這并不是特別有用。
計算時間復雜度通常更有用，讓一切都是變數，即我們可以想象在資料上運行您的演算法，其中可以有任意多個團隊，而不僅僅是 26 個團隊；我們只需要一種新的輸入格式。所以讓我們讓球隊的數量和選民的數量一樣成為一個變數。
如果n是團隊m數，是選民數，則構建哈希圖就是O(n*m)時間。O(n log(n))假設我們使用基于比較的排序，每次您對團隊進行排序時都會如此。您將在大多數情況下對團隊進行排序m 1：每個選民一次加上按字母順序排列一次。這意味著時間復雜度是O(m * n * log(n))——我們可以忽略 1 常數，因為它只會導致一個額外的n log(n)項，這與整個運行時間相比相形見絀，我們可以忽略構建哈希表，因為它只發生一次并且也相形見絀整個運行時間。
空間復雜度取決于哈希表使用的內容；它的O(m*n)大小。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/529175.html
上一篇：堆排序實作Python
下一篇：為什么我在二分搜索中需要 -1？