What is the main pattern used in 'Find the Most Common Response'?

The primary pattern is array scanning combined with hash map lookup to efficiently count occurrences and handle ties.

How do I handle ties in the frequency of responses?

If multiple responses have the same frequency, return the lexicographically smallest one.

What is the time complexity of this problem?

The time complexity is O(N * M), where N is the number of days and M is the number of responses per day.

Why do I need to remove duplicates within each day?

Duplicates within each day would distort the frequency count and lead to incorrect results. Removing them ensures accuracy.

Can I solve this problem without using hash maps?

While it's possible, hash maps provide an efficient way to count frequencies and are optimal for this task, especially with large inputs.

#3527

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找到最常见的回答

给你一个二维字符串数组 responses ，其中每个 responses[i] 是一个字符串数组，表示第 i 天调查的回答结果。请返回在对每个 responses[i] 中的回答去重后，所有天数中最常见的回答。如果有多个回答出现频率相同，则返回字典序最小的那个回答。示例 1：输入…

数组哈希表字符串计数

题目描述

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

lightbulb

解题思路

方法一：哈希表

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

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

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

1

2

3

4

5

6

7

8

9

10

11

12

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently handle large input sizes?
question_mark
Does the candidate apply hash maps effectively for counting frequencies?
question_mark
How well does the candidate handle tie-breaking between lexicographically equal counts?

warning

常见陷阱

外企场景

error
Not removing duplicates within each day before counting frequencies can lead to incorrect results.
error
Failure to account for ties in frequency, which may lead to returning the wrong response.
error
Inefficient handling of large input sizes, especially with array scanning or hash lookup.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handle responses with varying case sensitivity (e.g., 'good' vs 'Good').
arrow_right_alt
Find the second most common response instead of the first.
arrow_right_alt
Return the least common response instead of the most common.

help

常见问题

外企场景

继续练习

#3035 回文字符串的最大数量 #3522 执行指令后的得分 #3518 最小回文排列 II