Đạt có đề này, mọi người vào giải cho vui.
Nhập vào một chuỗi, xuất ra danh sách các từ trong câu và số lần xuất hiện theo thứ tự giảm dần. Không tính khoảng trống, dấu câu, ký tự khác
Ví dụ
intput
“day nhau hoc. hoc nhau day. HOC hoc ??
day day. day MA khong hoc.”
ouput
hoc : 5
day : 5
nhau : 2
khong : 1
ma : 1
Yêu cầu thêm:
Được dùng mọi ngôn ngữ
chử HOC vs hoc có khác nhau không a :D, phải khác nhau chứ
Dùng Python libraries, mẫu thử 1000 lần 
import re, time
from collections import Counter
SAMPLE = 1000
str = "day nhau hoc. hoc nhau day. HOC hoc ?? ^_^ day day. day MA khong hoc."
start = "%.50f" % time.time()
print(Counter(re.compile('[^a-zA-Z\s]').sub('', str).split()))
for i in range(0,SAMPLE-1):
Counter(re.compile('[^a-zA-Z\s]').sub('', str).split())
stop = "%.50f" % time.time()
print((float(stop) - float(start))/SAMPLE),
print("(s)")
Output:
Counter({'day': 5, 'hoc': 4, 'nhau': 2, 'MA': 1, 'HOC': 1, 'khong': 1})
9.0000629425e-06 (s)
Time complexity: ~10 us
Space complexity: đang tìm hiểu 
Dùng radix sort
def split_word(s):
s=s.lower()
i=0
ans=[]
while i<len(s):
if s[i].isalpha():
word=""
while s[i].isalpha() and i<len(s):
word+=s[i]
i+=1
ans.append(word)
i+=1
return ans
def radix_sort(lst,i):
if len(lst)<=1:
return lst
sorted_list=[]
bucket=[[] for x in range(26)]
for word in lst:
if i>=len(word):
sorted_list.append(word)
else:
bucket[ord(word[i])-ord('a')].append(word)
sorted_bucked=[radix_sort(b,i+1) for b in bucket]
return sorted_list+[word for lst in sorted_bucked for word in lst]
def counter(lst):
ans=[]
for v in lst:
if len(ans)==0 or v!=ans[-1][0]:
ans.append([v,1])
else:
ans[-1][1]+=1
return ans
for k,v in sorted(counter( radix_sort(split_word("day nhau hoc. hoc nhau day. \
HOC hoc ?? ^_^ day day. day MA khong hoc."),0)),reverse=True,key=lambda x:x[1]):
print k,":",v
Time, space : O(n*|w|)
Tận dụng mọi thứ có thể của java
package test;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class Test {
public static void main(String[] args) {
Map<String, Integer> mapString = new HashMap<String, Integer>();
String sourceStr = "day nhau hoc. hoc nhau day. HOC hoc ?? ^_^ day day. day MA khong hoc".toLowerCase();
String[] des = sourceStr.split("[^a-zA-Z0-9']+");
System.out.println(Arrays.asList(des));
mapString.put(des[0], 1);
for (int i = 1; i < des.length; i++) {
if (mapString.containsKey(des[i])) {
int currentVal = mapString.get(des[i]);
mapString.put(des[i], ++currentVal);
} else {
mapString.put(des[i], 1);
}
}
Map<String, Integer> sortedMap = sortByValue(mapString);
for (Map.Entry m : sortedMap.entrySet()) {
System.out.println(m.getKey() + " " + m.getValue());
}
}
private static Map<String, Integer> sortByValue(Map<String, Integer> unsortMap) {
// 1. Convert Map to List of Map
List<Map.Entry<String, Integer>> list = new LinkedList<Map.Entry<String, Integer>>(unsortMap.entrySet());
// 2. Sort list with Collections.sort(), provide a custom Comparator
// Try switch the o1 o2 position for a different order
Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
return (o2.getValue()).compareTo(o1.getValue());
}
});
// 3. Loop the sorted list and put it into a new insertion order Map
// LinkedHashMap
Map<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();
for (Map.Entry<String, Integer> entry : list) {
sortedMap.put(entry.getKey(), entry.getValue());
}
return sortedMap;
}
}
Mọi người giải thích thuật toán của mình ra luôn được không? Vì bài này mình cho phép dùng mọi ngôn ngữ, nên tốt nhất là nói luôn giải thuật để người khác đọc vào hiểu được.
P/S: Đạt không nghĩ là bài này lại có nhiều giải pháp overkill như vậy.
P/S2: Đạt giải bài này dùng cách tương tự như @nguyenhuuca, dùng unordered_map
Bước 1: Tách từng từ trong chuỗi ra
Bước 2: Dùng mỗi từ là key trong unordered_map, value là count của từ đó. Với cách này mình sẽ có O(n)
Bước 3: Chuyển cái kết quả từ map sang vector, sort lại. Với bước này mình sẽ tốn O(mlogm) với m là số lượng từ đã sắp xếp trong câu. m <= n.
Tổng phức tạp của bài này là O(n + mlogm), giả sử m << n thì coi như O(n)
Space complexity: O(m), với m là số lượng từ trong trong kết quả
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<pair<string, int>> solution(string inputStr) {
string word;
unordered_map<string, int> map;
for(char c : inputStr) {
if(isspace(c)) {
if (!word.empty()) {
map[word]++;
word.clear();
}
} else if (isalnum(c)){
word.push_back(tolower(c));
}
}
map[word]++;
vector<pair<string, int>> ans;
for(auto p : map) {
ans.push_back(make_pair(p.first, p.second));
}
sort(ans.begin(), ans.end(), [](const std::pair<string,int> &left, const std::pair<string,int> &right){
return left.second > right.second;
});
return ans;
}
int main() {
vector<pair<string, int>> ans = solution("day nhau hoc. hoc nhau day. ?? ^_^ HOC hoc day day. day MA khong hoc.");
for(auto e : ans) {
cout << e.first << " : " << e.second << endl;
}
}
Cái em dùng giống anh Đạt rồi, khỏi giải thích nhỉ :))
tính cmt mà ai cũng đưa sol hết rồi :’(
Kiếm bài khác đưa lên giải chơi Phúc.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?