題目敘述 Kth Distinct String in an Array
給定一個輸入陣列arr 和 參數k
請返回第k個出現恰好一次的陣列元素。測試範例
Example 1:
Input: arr = ["d","b","c","b","c","a"], k = 2
Output: "a"
Explanation:
The only distinct strings in arr are "d" and "a".
"d" appears 1st, so it is the 1st distinct string.
"a" appears 2nd, so it is the 2nd distinct string.
Since k == 2, "a" is returned.
Example 2:
Input: arr = ["aaa","aa","a"], k = 1
Output: "aaa"
Explanation:
All strings in arr are distinct, so the 1st string "aaa" is returned.
約束條件
Constraints:
1 <= k <= arr.length <= 1000
1 <= 參數k值 <= 輸入陣列長度 <= 一千
1 <= arr[i].length <= 5
每個陣列元素的長度介於1~5之間。
arr[i]consists of lowercase English letters.
陣列元素只會有小寫英文字母組成的字串。
演算法 字典統計每個出現次數
建立一個字典。
掃描每個陣列元素，統計每個陣列元素的出現次數。
每遇到一個出現一次的陣列元素，k值就減一。
當k值等於零的時候，當下的元素就是第k個恰好出現一次的陣列元素。
程式碼 字典統計每個出現次數
class Solution:
def kthDistinct(self, arr: List[str], k: int) -> str:
# key: unique string
# value: occurrence
str_occ_dict = Counter(arr)
for element in arr:
if str_occ_dict[element] == 1:
# find one distinct string, subtract counter k with 1
k -= 1
if k == 0:
# kth distinct string is current element
return element
return ""
複雜度分析
時間複查度: O(n)
從左到右掃描每個陣列元素，所需時間為O(n)
空間複查度: O(n)
建立一個字典，儲存每個陣列元素的出現次數，最多所需空間為O(n)
