字典應用: 第k個出現一次的字串 Kth Distinct String in an Array_LC #2053

Rashed Paykary on Unsplash

題目敘述 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)

Reference

[1] Kth Distinct String in an Array - LeetCode