2053. 數組中第 K 個獨一無二的字符串

獨一無二的字符串?指的是在一個數組中只出現過 一次?的字符串。

給你一個字符串數組?arr?和一個整數?k?，請你返回?arr?中第?k?個?獨一無二的字符串?。如果?少于?k?個獨一無二的字符串，那么返回?空字符串?“”?。

注意，按照字符串在原數組中的 順序?找到第 k?個獨一無二字符串。

示例 1:
輸入：arr = ["d","b","c","b","c","a"], k = 2
輸出："a"
解釋：
arr 中獨一無二字符串包括 "d" 和 "a"?。
"d" 首先出現，所以它是第 1 個獨一無二字符串。
"a" 第二個出現，所以它是 2 個獨一無二字符串。
由于 k == 2 ，返回 "a" 。示例 2:
輸入：arr = ["aaa","aa","a"], k = 1
輸出："aaa"
解釋：
arr 中所有字符串都是獨一無二的，所以返回第 1 個字符串 "aaa" 。示例 3：
輸入：arr = ["a","b","a"], k = 3
輸出：""
解釋：
唯一一個獨一無二字符串是 "b" 。由于少于 3 個獨一無二字符串，我們返回空字符串 "" 。

提示：

• 1 <= k <= arr.length <= 1000
• 1 <= arr[i].length <= 5
• arr[i]?只包含小寫英文字母。

解題思路

使用map維護字符串以及其在數組中出現次數的關系，再次遍歷數組，找出只出現一次的字符串，并且找出第k個出現次數為1次的字符串，如果出現次數小于1的字符串的個數小于k，則返回一個空串。

代碼

class Solution {
public:string kthDistinct(vector<string>& arr, int k) {map<string,int> m;for (int i = 0; i < arr.size(); ++i) {m[arr[i]]++;}for (int i = 0; i < arr.size(); ++i) {if (m[arr[i]]==1&&--k==0)return arr[i];}return "";}
};

• 時間復雜度：$O({\sum }_i{n}_i)$，即數組 $\text{arr}$ 中字符串長度總和，其中 $n_i$為字符串 $\text{arr}[i]$ 的長度。即為維護頻數哈希表和尋找第 k 個獨一無二的字符串的時間復雜度。

• 空間復雜度：$O({\sum }_i{n}_i)$，即為哈希集合的空間開銷。