Easy

题目描述

不同字符串是指在数组中只出现一次的字符串。

给你一个字符串数组 arr，以及一个整数 k，返回 arr 中第 k 个不同字符串。如果不同字符串少于 k 个，则返回空字符串 ""。

注意，字符串是按照它们在数组中出现的顺序来考虑的。

示例 1：

输入：arr = ["d","b","c","b","c","a"], k = 2
输出："a"
解释：
arr 中只有 "d" 和 "a" 是不同字符串。
"d" 排第 1 位，所以它是第 1 个不同字符串。
"a" 排第 2 位，所以它是第 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] 由小写英文字母组成

解题思路

解题思路

这道题需要找到数组中第 k 个只出现一次的字符串。

核心思路：

  1. 首先统计每个字符串的出现次数
  2. 然后按照原数组顺序遍历，找到出现次数为 1 的字符串
  3. 当找到第 k 个这样的字符串时返回，如果不足 k 个则返回空字符串

算法步骤：

  1. 使用哈希表统计每个字符串的出现频率
  2. 再次遍历原数组，对于每个出现次数为 1 的字符串，将计数器加 1
  3. 当计数器达到 k 时，返回当前字符串
  4. 遍历结束后如果仍未找到第 k 个，返回空字符串

时间复杂度分析：

  • 第一次遍历统计频率：O(n)
  • 第二次遍历寻找结果：O(n)
  • 总体时间复杂度：O(n)

这种解法简单直接，只需要两次遍历就能得到结果，是最优的解法。

代码实现

class Solution {
public:
    string kthDistinct(vector<string>& arr, int k) {
        unordered_map<string, int> count;
        
        // 统计每个字符串的出现次数
        for (const string& s : arr) {
            count[s]++;
        }
        
        // 寻找第k个不同字符串
        int distinctCount = 0;
        for (const string& s : arr) {
            if (count[s] == 1) {
                distinctCount++;
                if (distinctCount == k) {
                    return s;
                }
            }
        }
        
        return "";
    }
};

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        from collections import Counter
        
        # 统计每个字符串的出现次数
        count = Counter(arr)
        
        # 寻找第k个不同字符串
        distinct_count = 0
        for s in arr:
            if count[s] == 1:
                distinct_count += 1
                if distinct_count == k:
                    return s
        
        return ""

public class Solution {
    public string KthDistinct(string[] arr, int k) {
        Dictionary<string, int> count = new Dictionary<string, int>();
        
        // 统计每个字符串的出现次数
        foreach (string s in arr) {
            if (count.ContainsKey(s)) {
                count[s]++;
            } else {
                count[s] = 1;
            }
        }
        
        // 寻找第k个不同字符串
        int distinctCount = 0;
        foreach (string s in arr) {
            if (count[s] == 1) {
                distinctCount++;
                if (distinctCount == k) {
                    return s;
                }
            }
        }
        
        return "";
    }
}

var kthDistinct = function(arr, k) {
    const count = {};
    
    for (const str of arr) {
        count[str] = (count[str] || 0) + 1;
    }
    
    let distinctCount = 0;
    for (const str of arr) {
        if (count[str] === 1) {
            distinctCount++;
            if (distinctCount === k) {
                return str;
            }
        }
    }
    
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，每次O(n)
空间复杂度O(n)哈希表存储字符串频率，最坏情况下所有字符串都不同

相关题目