数组
哈希表
字符串
计数
题目描述
给你一个聊天记录,共包含 n
条信息。给你两个字符串数组 messages
和 senders
,其中 messages[i]
是 senders[i]
发出的一条 信息 。
一条 信息 是若干用单个空格连接的 单词 ,信息开头和结尾不会有多余空格。发件人的 单词计数 是这个发件人总共发出的 单词数 。注意,一个发件人可能会发出多于一条信息。
请你返回发出单词数 最多 的发件人名字。如果有多个发件人发出最多单词数,请你返回 字典序 最大的名字。
注意:
字典序里,大写字母小于小写字母。
"Alice"
和 "alice"
是不同的名字。
示例 1:
输入: messages = ["Hello userTwooo","Hi userThree","Wonderful day Alice","Nice day userThree"], senders = ["Alice","userTwo","userThree","Alice"]
输出: "Alice"
解释: Alice 总共发出了 2 + 3 = 5 个单词。
userTwo 发出了 2 个单词。
userThree 发出了 3 个单词。
由于 Alice 发出单词数最多,所以我们返回 "Alice" 。
示例 2:
输入: messages = ["How is leetcode for everyone","Leetcode is useful for practice"], senders = ["Bob","Charlie"]
输出: "Charlie"
解释: Bob 总共发出了 5 个单词。
Charlie 总共发出了 5 个单词。
由于最多单词数打平,返回字典序最大的名字,也就是 Charlie 。
提示:
n == messages.length == senders.length
1 <= n <= 104
1 <= messages[i].length <= 100
1 <= senders[i].length <= 10
messages[i]
包含大写字母、小写字母和 ' '
。
messages[i]
中所有单词都由 单个空格 隔开。
messages[i]
不包含前导和后缀空格。
senders[i]
只包含大写英文字母和小写英文字母。
解法
方法一:哈希表 + 枚举
我们用哈希表 cnt
统计每个发件人的单词数,然后枚举每个发件人,找到单词数最多且字典序最大的发件人即可。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为 messages
的长度。
Python3 Java C++ Go
class Solution :
def largestWordCount ( self , messages : List [ str ], senders : List [ str ]) -> str :
cnt = Counter ()
for msg , sender in zip ( messages , senders ):
cnt [ sender ] += msg . count ( ' ' ) + 1
ans = ''
for sender , v in cnt . items ():
if cnt [ ans ] < v or ( cnt [ ans ] == v and ans < sender ):
ans = sender
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public String largestWordCount ( String [] messages , String [] senders ) {
Map < String , Integer > cnt = new HashMap <> ();
int n = senders . length ;
for ( int i = 0 ; i < n ; ++ i ) {
int v = 1 ;
for ( int j = 0 ; j < messages [ i ] . length (); ++ j ) {
if ( messages [ i ] . charAt ( j ) == ' ' ) {
++ v ;
}
}
cnt . merge ( senders [ i ] , v , Integer :: sum );
}
String ans = senders [ 0 ] ;
for ( var e : cnt . entrySet ()) {
String sender = e . getKey ();
if ( cnt . get ( ans ) < cnt . get ( sender )
|| ( cnt . get ( ans ) == cnt . get ( sender ) && ans . compareTo ( sender ) < 0 )) {
ans = sender ;
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public :
string largestWordCount ( vector < string >& messages , vector < string >& senders ) {
unordered_map < string , int > cnt ;
int n = senders . size ();
for ( int i = 0 ; i < n ; ++ i ) {
int v = count ( messages [ i ]. begin (), messages [ i ]. end (), ' ' ) + 1 ;
cnt [ senders [ i ]] += v ;
}
string ans = senders [ 0 ];
for ( auto & [ sender , v ] : cnt ) {
if ( cnt [ ans ] < v || ( cnt [ ans ] == v && ans < sender )) {
ans = sender ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13 func largestWordCount ( messages [] string , senders [] string ) ( ans string ) {
cnt := map [ string ] int {}
for i , msg := range messages {
v := strings . Count ( msg , " " ) + 1
cnt [ senders [ i ]] += v
}
for sender , v := range cnt {
if cnt [ ans ] < v || ( cnt [ ans ] == v && ans < sender ) {
ans = sender
}
}
return
}
GitHub