🔗 🟢 2053. Kth Distinct String in an Array 1351

tags: `Biweekly Contest 64` `陣列(Array)` `字串(String)` `雜湊表(Hash Table)` `計數(Counting)`

題意

獨特字串 是指在陣列中只出現一次的字串。

給定一個字串陣列 $arr$ 和一個整數 $k$ ，返回 $arr$ 中第 $k$ 個 獨特字串 。如果獨特字串少於 $k$ 個，則返回空字串 ""。

注意，字串的順序是按照它們在陣列中出現的順序考慮的。

思路：雜湊表(Hash Table)

為了找到所有的獨特字串，我們可以使用一個雜湊表(Hash Table) $cnt$ 來記錄每個字串的出現次數，其中 $cnt[s]$ 表示字串 $s$ 出現的次數。

由於獨特字串的順序和字串陣列 $arr$ 的順序相同，因此在統計完出現次數後，可以重新遍歷一次字串陣列 $arr$ ，若 $arr[i]$ 的出現次數為 $1$ ，則將 $k$ 减 $1$ ，如果 $k$ 為 $0$ ，代表此時的 $arr[i]$ 就是第 $k$ 個獨特字串，因此可以直接返回 $arr[i]$ 。

複雜度分析

時間複雜度： $O(\Sigma n_i)$ ，其中 $n_i$ 表示字串 $arr[i]$ 的大小，需要遍歷字串陣列 $2$ 次。
空間複雜度： $O(\Sigma n_i)$ ，雜湊表所需要的空間。

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        cnt = Counter(arr)
        for s in arr:
            if cnt[s] == 1:
                k -= 1
                if k == 0:
                    return s
        return ''

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k) {
        unordered_map<string, int> cnt;
        for (auto& s : arr) cnt[s]++;
        for (auto& s : arr)
            if (cnt[s] == 1 && --k == 0) return s;
        return "";
    }
};