3527. 找到最常见的回答

English Version

题目描述

给你一个二维字符串数组 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] 仅由小写英文字母组成

解法

方法一：哈希表

我们可以用一个哈希表 $\textit{cnt}$ 来统计每个回答的出现次数。对于每一天的回答，我们先去重，然后将每个回答加入哈希表中，更新其出现次数。

最后，我们遍历哈希表，找到出现次数最多的回答。如果有多个回答出现次数相同，则返回字典序最小的那个回答。

时间复杂度 $O(L)$，空间复杂度 $O(L)$。其中 $L$ 是所有回答的总长度。

Python3

class Solution:
    def findCommonResponse(self, responses: List[List[str]]) -> str:
        cnt = Counter()
        for ws in responses:
            for w in set(ws):
                cnt[w] += 1
        ans = responses[0][0]
        for w, x in cnt.items():
            if cnt[ans] < x or (cnt[ans] == x and w < ans):
                ans = w
        return ans

Java

class Solution {
    public String findCommonResponse(List<List<String>> responses) {
        Map<String, Integer> cnt = new HashMap<>();
        for (var ws : responses) {
            Set<String> s = new HashSet<>();
            for (var w : ws) {
                if (s.add(w)) {
                    cnt.merge(w, 1, Integer::sum);
                }
            }
        }
        String ans = responses.get(0).get(0);
        for (var e : cnt.entrySet()) {
            String w = e.getKey();
            int v = e.getValue();
            if (cnt.get(ans) < v || (cnt.get(ans) == v && w.compareTo(ans) < 0)) {
                ans = w;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    string findCommonResponse(vector<vector<string>>& responses) {
        unordered_map<string, int> cnt;
        for (const auto& ws : responses) {
            unordered_set<string> s;
            for (const auto& w : ws) {
                if (s.insert(w).second) {
                    ++cnt[w];
                }
            }
        }
        string ans = responses[0][0];
        for (const auto& e : cnt) {
            const string& w = e.first;
            int v = e.second;
            if (cnt[ans] < v || (cnt[ans] == v && w < ans)) {
                ans = w;
            }
        }
        return ans;
    }
};

Go

func findCommonResponse(responses [][]string) string {
	cnt := map[string]int{}
	for _, ws := range responses {
		s := map[string]struct{}{}
		for _, w := range ws {
			if _, ok := s[w]; !ok {
				s[w] = struct{}{}
				cnt[w]++
			}
		}
	}
	ans := responses[0][0]
	for w, v := range cnt {
		if cnt[ans] < v || (cnt[ans] == v && w < ans) {
			ans = w
		}
	}
	return ans
}

TypeScript

function findCommonResponse(responses: string[][]): string {
    const cnt = new Map<string, number>();
    for (const ws of responses) {
        const s = new Set<string>();
        for (const w of ws) {
            if (!s.has(w)) {
                s.add(w);
                cnt.set(w, (cnt.get(w) ?? 0) + 1);
            }
        }
    }
    let ans = responses[0][0];
    for (const [w, v] of cnt) {
        const best = cnt.get(ans)!;
        if (best < v || (best === v && w < ans)) {
            ans = w;
        }
    }
    return ans;
}