Medium

题目描述

给你一个二维字符串数组 responses，其中 responses[i] 是一个字符串数组，表示第 i 天的调查回复。

在移除每个 responses[i] 中的重复回复后，返回所有天数中最常见的回复。如果有多个回复出现次数相同，返回字典序最小的回复。

示例 1：

输入：responses = [["good","ok","good","ok"],["ok","bad","good","ok","ok"],["good"],["bad"]]
输出："good"
解释：
移除每个列表中的重复项后，responses = [["good", "ok"], ["ok", "bad", "good"], ["good"], ["bad"]]。
"good" 出现 3 次，"ok" 出现 2 次，"bad" 出现 2 次。
返回 "good"，因为它的频率最高。

示例 2：

输入：responses = [["good","ok","good"],["ok","bad"],["bad","notsure"],["great","good"]]
输出："bad"
解释：
移除每个列表中的重复项后，responses = [["good", "ok"], ["ok", "bad"], ["bad", "notsure"], ["great", "good"]]。
"bad"、"good" 和 "ok" 各出现 2 次。
输出 "bad"，因为在具有最高频率的单词中它的字典序最小。

约束条件：

  • 1 <= responses.length <= 1000
  • 1 <= responses[i].length <= 1000
  • 1 <= responses[i][j].length <= 10
  • responses[i][j] 仅由小写英文字母组成

提示：

  • 使用哈希表。

解题思路

这道题需要我们找到所有天数中出现频率最高的回复，并且在频率相同时选择字典序最小的。

解题思路分为几个步骤：

  1. 去重处理：对于每一天的回复列表，我们需要先去除重复的回复。可以使用集合（Set）来实现去重。

  2. 频率统计：使用哈希表来统计每个唯一回复在所有天数中的出现次数。遍历去重后的每一天回复，累加每个回复的出现频率。

  3. 找到最优解：遍历哈希表，找到出现频率最高的回复。如果有多个回复频率相同，选择字典序最小的那个。

具体实现中，我们可以：

  • 对每一天的回复使用集合去重
  • 用哈希表记录每个回复的总出现天数
  • 最后遍历哈希表找到频率最高且字典序最小的回复

时间复杂度主要来自于遍历所有回复和去重操作，空间复杂度主要是哈希表存储各回复的频率。

代码实现

class Solution {
public:
    string findCommonResponse(vector<vector<string>>& responses) {
        unordered_map<string, int> freq;
        
        for (auto& dayResponses : responses) {
            unordered_set<string> uniqueResponses(dayResponses.begin(), dayResponses.end());
            for (const string& response : uniqueResponses) {
                freq[response]++;
            }
        }
        
        int maxFreq = 0;
        string result = "";
        
        for (const auto& pair : freq) {
            if (pair.second > maxFreq || (pair.second == maxFreq && pair.first < result)) {
                maxFreq = pair.second;
                result = pair.first;
            }
        }
        
        return result;
    }
};

class Solution:
    def findCommonResponse(self, responses: List[List[str]]) -> str:
        freq = {}
        
        for day_responses in responses:
            unique_responses = set(day_responses)
            for response in unique_responses:
                freq[response] = freq.get(response, 0) + 1
        
        max_freq = 0
        result = ""
        
        for response, count in freq.items():
            if count > max_freq or (count == max_freq and response < result):
                max_freq = count
                result = response
        
        return result

public class Solution {
    public string FindCommonResponse(IList<IList<string>> responses) {
        var freq = new Dictionary<string, int>();
        
        foreach (var dayResponses in responses) {
            var uniqueResponses = new HashSet<string>(dayResponses);
            foreach (var response in uniqueResponses) {
                if (freq.ContainsKey(response)) {
                    freq[response]++;
                } else {
                    freq[response] = 1;
                }
            }
        }
        
        int maxFreq = 0;
        string result = "";
        
        foreach (var pair in freq) {
            if (pair.Value > maxFreq || (pair.Value == maxFreq && (result == "" || string.Compare(pair.Key, result) < 0))) {
                maxFreq = pair.Value;
                result = pair.Key;
            }
        }
        
        return result;
    }
}

var findCommonResponse = function(responses) {
    const frequency = new Map();
    
    for (const response of responses) {
        const unique = [...new Set(response)];
        for (const word of unique) {
            frequency.set(word, (frequency.get(word) || 0) + 1);
        }
    }
    
    let maxFreq = 0;
    let result = "";
    
    for (const [word, freq] of frequency) {
        if (freq > maxFreq || (freq === maxFreq && word < result)) {
            maxFreq = freq;
            result = word;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(N × M)其中 N 是天数，M 是每天平均回复数。需要遍历所有回复进行去重和统计
空间复杂度O(K)其中 K 是所有唯一回复的总数，用于存储频率哈希表和临时集合

相关题目