【Day 88 】2021-12-06 - 451 根据字符出现频率排序 #107
Comments
思路:基于哈希表 + sort来做 代码:实现语言: C++ class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> dict;
for (auto& ch : s)
{
if (dict.find(ch) == dict.end())
dict[ch] = 1;
else dict[ch]++;
}
string res;
vector<pair<char, int>> kvVect;
for (auto& kvp : dict)
kvVect.push_back(kvp);
auto cmp = [](const pair<char, int>& p1, const pair<char, int>& p2)
{
return p1.second > p2.second;
};
sort(kvVect.begin(), kvVect.end(), cmp);
for (auto& kvp : kvVect)
{
while (kvp.second--)
res.push_back(kvp.first);
}
return res;
}
};复杂度分析:
|
代码class Solution {
public String frequencySort(String s) {
HashMap<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
int frequency = map.getOrDefault(c, 0) + 1;
map.put(c, frequency);
}
StringBuilder sb = new StringBuilder();
List<Character> list = new ArrayList<>(map.keySet());
Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
for (Character c : list) {
int frequency = map.get(c);
while (frequency-- > 0) sb.append(c);
}
return sb.toString();
}
} |
|
思路：堆+哈希表 时间复杂度: O(NlogN) |
class Solution:
def frequencySort(self, s: str) -> str:
fre = collections.Counter(s)
fre_list = sorted(fre.items(), key = lambda x: x[1], reverse = True)
result = ""
for k, v in fre_list:
result += k * v
return result |
解题思路堆+哈希表。建立哈希表储存字符和字符出现的频率。建立大顶堆，将哈希表中的字符放入堆中，然后每次从堆中取出当前出现频率最高的字符，加入到StringBuilder。最后返回字符串即可。 代码class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
map.put(c, map.getOrDefault(c, 0) + 1);
}
PriorityQueue<Character> heap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
for (char key : map.keySet()) {
heap.offer(key);
}
StringBuilder sb = new StringBuilder();
while (!heap.isEmpty()) {
char cur = heap.poll();
int count = map.get(cur);
while (count > 0) {
sb.append(cur);
count--;
}
}
return sb.toString();
}
}复杂度分析
|
关键点代码
C++ Code: class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> record;
for(int i=0; i< s.size(); i++)
{
record[s[i]]++;
}
multimap<int, char, greater<int>> sortNum;
for(auto it = record.begin(); it!=record.end(); it++)
{
sortNum.insert(make_pair((*it).second, (*it).first));
}
string ret;
for(auto it = sortNum.begin(); it!= sortNum.end(); it++)
{
for(int i=0; i< (*it).first; i++)
ret.push_back((*it).second);
}
return ret;
}
};
|
IdeaHeap + Hash table. The hash table is used to record the frequency of the char in the string. The heap is used to sort the char based on its frequency. Each node in the heap will be a tuple containing with two elements: the negative value of the char's frequency and char. The build the answer based on the heap. Code:class Solution:
def frequencySort(self, s: str) -> str:
count = collections.Counter(s)
heap = []
for i in count:
heapq.heappush(heap, (-count[i], i))
ans = ""
while heap:
i, c = heapq.heappop(heap)
ans += abs(i) *c
return ansComplexity:Time: O(N + k log k) N: length of the string. K: amount of the unique chars. |
link:https://leetcode.com/problems/sort-characters-by-frequency/ 代码 Javascriptconst frequencySort = function (s) {
let seen = {};
for (let char of s) {
seen[char] ? seen[char]++ : (seen[char] = 1);
}
let SortedCharactersArray = Object.keys(seen).sort(
(a, b) => seen[b] - seen[a]
);
let result = '';
for (let char of SortedCharactersArray) result += char.repeat(seen[char]);
return result;
}; |
思路
Java Code public String frequencySort(String s) {
int n = s.length();
Map<Character, Integer> countMap = new HashMap();
for (char c : s.toCharArray()) {
countMap.put(c, countMap.getOrDefault(c, 0) + 1);
}
List<Character>[] buckets = new ArrayList[n + 1];
for (char c : countMap.keySet()) {
if (buckets[countMap.get(c)] == null) {
buckets[countMap.get(c)] = new ArrayList<>();
}
buckets[countMap.get(c)].add(c);
}
StringBuilder sb = new StringBuilder();
for (int i = n; i >=0; i--) {
if (buckets[i] != null) {
for (char c : buckets[i]) {
for (int j = 0; j < i; j++) {
sb.append(c);
}
}
}
}
return sb.toString();
}时间&空间
|
method 1:thoughthash + sorted codecomplexityTime: O(N+KlogK) N: length of s, K: num of diff chars in s (== num of keys in hash); logK?? space: O(N + K) method2thoughtBucket sorting complexityTime: O(N+ K) N: length of s, K: num of diff chars in s (== num of keys in hash) |
class Solution:
def frequencySort(self, s: str) -> str:
counter = {}
res = ''
for char in s:
counter[char] = counter.get(char, 0) + 1
for char, count in sorted(counter.items(), key = lambda x: -x[1]):
res += char * count
return res |
Note
Solutionclass Solution:
def frequencySort(self, s: str) -> str:
d = {}
for c in s:
d[c] = d.get(c, 0) + 1
tmp = sorted(d.items(), key=lambda x: x[1], reverse=True)
res = ''
for k, v in tmp:
res += k * v
return resTime complexity: O(NlogN) Space complexity: O(N) |
|
Naive Approach public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
List<Character> letterOrder = new ArrayList<>(map.keySet());
Collections.sort(letterOrder, (a, b) -> (map.get(b) - map.get(a)));
StringBuilder sb = new StringBuilder();
for (char c : letterOrder) {
int frequency = map.get(c);
for (int i = 0; i < frequency; i++) {
sb.append(c);
}
}
String res = sb.toString();
return res;
} |
func frequencySort(s string) string {
hash := map[byte]int{}
for i:= range s{
hash[s[i]]++
}
type pair struct{
ch byte
count int
}
pairs := make([]pair,len(hash))
for k,v := range hash{
pairs = append(pairs,pair{k,v})
}
sort.Slice(pairs,func(i,j int)bool{
return pairs[i].count > pairs[j].count
})
out := ""
for _,x := range pairs{
out += strings.Repeat(string(x.ch),x.count)
}
return out
} |
思路哈希表。 代码(C++)class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> mp;
int length = s.length();
for (auto &ch : s) mp[ch]++;
vector<pair<char, int>> vec;
for (auto &it : mp) vec.emplace_back(it);
sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
return a.second > b.second;
});
string ret;
for (auto &[ch, num] : vec) for (int i = 0; i < num; i++) ret.push_back(ch);
return ret;
}
};复杂度分析
|
thoughts先计数，然后根据计数逆序排序 最后拼装 codefrom collections import defaultdict
class Solution:
def frequencySort(self, s: str) -> str:
char_count_dict = defaultdict(int)
for char in s:
char_count_dict[char] += 1
char_freq_sorted_list = sorted(char_count_dict.items(), key=lambda item: item[1], reverse = True)
result = ''
for char, freq in char_freq_sorted_list:
result += freq * char
return resultcomplexityTime O(nlgn) Space O(n) |
代码
Java Code: public class Solution {
/**
* @param s:
* @return: return a string
*/
public String frequencySort(String s) {
Map<Character, Integer> frequency = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
if (!frequency.containsKey(s.charAt(i))) {
frequency.put(s.charAt(i), 0);
}
frequency.put(s.charAt(i), frequency.get(s.charAt(i)) + 1);
}
List<Pair> pairs = new LinkedList<Pair>();
for (char key : frequency.keySet()) {
pairs.add(new Pair(key, frequency.get(key)));
}
Collections.sort(pairs, new Comparator<Pair>() {
public int compare(Pair a, Pair b) {
if (a.frequency == b.frequency) {
return (int)a.letter - (int)b.letter;
}
return b.frequency - a.frequency;
}
});
StringBuffer result = new StringBuffer("");
for (Pair pair : pairs) {
for (int i = 0; i < pair.frequency; i++) {
result.append(pair.letter);
}
}
return result.toString();
}
}
class Pair {
char letter;
int frequency;
public Pair(char letter, int frequency) {
this.letter = letter;
this.frequency = frequency;
}
} |
public String frequencySort(String s) {
int n = s.length();
Map<Character, Integer> countMap = new HashMap();
for (char c : s.toCharArray()) {
countMap.put(c, countMap.getOrDefault(c, 0) + 1);
}
List<Character>[] buckets = new ArrayList[n + 1];
for (char c : countMap.keySet()) {
if (buckets[countMap.get(c)] == null) {
buckets[countMap.get(c)] = new ArrayList<>();
}
buckets[countMap.get(c)].add(c);
}
StringBuilder sb = new StringBuilder();
for (int i = n; i >=0; i--) {
if (buckets[i] != null) {
for (char c : buckets[i]) {
for (int j = 0; j < i; j++) {
sb.append(c);
}
}
}
}
return sb.toString();
} |
思路使用堆进行排序 先对词频进行统计 然后将所有 (-frequency, character) 加入堆中 (因为想要大顶堆所以取负数) 然后每次从堆中取出堆顶元素赋值 frequency 遍加入 res string 中 from collections import Counter, defaultdict
import heapq
class Solution:
def frequencySort(self, s: str) -> str:
count = Counter(s)
reverse = defaultdict(list)
h = []
for k, v in count.items():
h.append((-v, k))
heapq.heapify(h)
res = ''
while h:
v, s = heapq.heappop(h)
res += (-v)*s
return res复杂度时间复杂度: O(nlogn) 堆的时间复杂度为 O(nlogn) 遍历统计的时间复杂度为 O(n) 空间复杂度: O(n) 堆的空间复杂度 |
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
int frequency = map.getOrDefault(c, 0) + 1;
map.put(c, frequency);
}
List<Character> list = new ArrayList<Character>(map.keySet());
Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
StringBuffer sb = new StringBuffer();
int size = list.size();
for (int i = 0; i < size; i++) {
char c = list.get(i);
int frequency = map.get(c);
for (int j = 0; j < frequency; j++) {
sb.append(c);
}
}
return sb.toString();
}
} |
题目
代码复杂度Space: O(n) |
var frequencySort = function (s) {
let map = new Map();
for (let i of s) {
let num = map.get(i) || 0;
map.set(i, ++num);
}
let res = "";
let arr = Array.from(map).sort((a, b) => b[1] - a[1]);
for (let [key, val] of arr) {
res += key.repeat(val);
}
return res;
}; |
思路链表 代码Python3 Code class Solution:
def frequencySort(self, s: str) -> str:
dict = {}
for ch in s:
dict[ch] = dict.get(ch, 0) + 1
vals = sorted(dict.items(), key=lambda x : x[1], reverse=True)
res = ""
for k, v in vals:
res += k * v
return res复杂度 设N为字符个数，K为去重字符个数
|
开始刷题题目简介【Day 88 】2021-12-06 - 451 根据字符出现频率排序题目思路
题目代码代码块class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> mp;
int length = s.length();
for (auto &ch : s) {
mp[ch]++;
}
vector<pair<char, int>> vec;
for (auto &it : mp) {
vec.emplace_back(it);
}
sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
return a.second > b.second;
});
string ret;
for (auto &[ch, num] : vec) {
for (int i = 0; i < num; i++) {
ret.push_back(ch);
}
}
return ret;
}
};
复杂度
|
思路使用哈希表存，然后使用排序再拼接字符串 var frequencySort = function(s) {
const map = new Map();
for (let i = 0; i < s.length; i++) {
let c = s[i];
map.set(c, (map.get(c) || 0) + 1);
}
return Array.from(map)
.sort((a, b) => b[1] - a[1])
.map(item => item[0].repeat(item[1]))
.join('')
}; |
思路先遍历字符串获取词频哈希表，再将哈希表存到vector中来实现按value排序，最后拼接返回结果字符串 代码class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> mp;
int length = s.length();
for (auto &ch : s) {
mp[ch]++;
}
vector<pair<char, int>> vec;
for (auto &it : mp) {
vec.emplace_back(it);
}
sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
return a.second > b.second;
});
string ret;
for (auto &[ch, num] : vec) {
for (int i = 0; i < num; i++) {
ret.push_back(ch);
}
}
return ret;
}
};复杂度O(n + klogk) |
题目https://leetcode-cn.com/problems/sort-characters-by-frequency/ 思路Heap python3class Solution:
def frequencySort(self, s: str) -> str:
dic = defaultdict(int)
for char in s:
dic[char] += 1
heap = []
for key, value in dic.items():
heapq.heappush(heap, (-value, key))
ans = []
while(heap):
freq, char = heapq.heappop(heap)
ans.append(-freq*char)
return ''.join(ans)复杂度分析
相关题目
|
Codeclass Solution:
def frequencySort(self, s: str) -> str:
dic = {}
for i in s:
if i not in dic:
dic[i] = 0
dic[i] += 1
sort = sorted(dic, key = dic.get, reverse = True)
res = ""
for k in sort:
res += k * dic[k]
return res |
func frequencySort(s string) string {
m := make(map[rune]int)
ret := make([]rune,0)//存放每一个字符
res := make([]rune,0)//存放结果
//注意！！要将s转成rune 因为使用for i,v:=range s的时候，这个v是rune的 最后return再转回来即可
r := []rune(s)
//这个for循环是得到string中每一个字符的频率，用一个数组存下字符
for _,v := range r {
//判断m这个map里面有没有v这个Key
i,ok := m[v]
if ok {//如果有的话则将m[v]的value＋1
m[v] = i+1 // 即m[v]++
}else{
m[v] = 1
ret = append(ret, v)
}
}
//按照频率的大小排序
sort.Slice(ret, func(i, j int) bool {
return m[ret[i]] > m[ret[j]]
})
//按照频率将每个字符复原成字符串
for i:=0;i<len(ret);i++{
for j:=0;j<m[ret[i]];j++{
res=append(res,ret[i])
}
}
return string(res)
} |
代码class Solution {
class Node{
char c;
int v;
Node(char c, int v) {
this.c = c;
this.v = v;
}
}
public String frequencySort(String s) {
if(s.isEmpty()) return "";
Map<Character, Integer> map = new HashMap<>();
for(int i = 0;i < s.length();i++) {
char temp = s.charAt(i);
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
PriorityQueue<Node> queue = new PriorityQueue<>( (a, b) -> {
if(a.v != b.v) {
return b.v -a.v;
}
return a.c - b.c;
});
for(char c : map.keySet()) {
queue.add(new Node(c, map.get(c)));
}
StringBuilder sb = new StringBuilder();
while(!queue.isEmpty()) {
Node res = queue.poll();
int value = res.v;
while(value-- >0) {
sb.append(res.c);
}
}
return sb.toString();
}
}复杂度
|
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> dict;
for (auto& ch : s)
{
if (dict.find(ch) == dict.end())
dict[ch] = 1;
else dict[ch]++;
}
string res;
vector<pair<char, int>> kvVect;
for (auto& kvp : dict)
kvVect.push_back(kvp);
auto cmp = [](const pair<char, int>& p1, const pair<char, int>& p2)
{
return p1.second > p2.second;
};
sort(kvVect.begin(), kvVect.end(), cmp);
for (auto& kvp : kvVect)
{
while (kvp.second--)
res.push_back(kvp.first);
}
return res;
}
}; |
|
Map<Character, Integer> map = new HashMap<Character, Integer>(); 时间复杂度：O(n+klogk) |
【Day 88】451 根据字符出现频率排序代码class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> mp;
int length = s.length();
for (auto &ch : s) {
mp[ch]++;
}
vector<pair<char, int>> vec;
for (auto &it : mp) {
vec.emplace_back(it);
}
sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
return a.second > b.second;
});
string ret;
for (auto &[ch, num] : vec) {
for (int i = 0; i < num; i++) {
ret.push_back(ch);
}
}
return ret;
}
};复杂度时间复杂度：O(NLogN) 空间复杂度：O(K) |
|
/**
|
|
class Solution { |
|
title: "Day 87 23. 合并K个升序链表" 451. 根据字符出现频率排序题目给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
"Aabb"
输出:
"bbAa"
解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。题目思路
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> up;
for(auto i : s) up[i]++;
sort(s.begin(), s.end(), [&](const char &a, const char &b) {
return up[a] == up[b] ? a > b : up[a] > up[b];
});
return s;
}
};复杂度
|
JAVA版本思路：直接使用堆来完成的，使用hashmap用来统计所有字母以及对应的个数，最后使用一个堆来完成排序，并输出。
时间复杂度：O(nlogn) 空间复杂度：O(n) |
思路：哈希表，然后遍历这个哈希表时间复杂度：O(n) |
string frequencySort(string s) {
unordered_map<char, int> mp;
for (char &ch : s){
++mp[ch];
}
auto cmp = [](pair<char, int>& a, pair<char, int>& b){return a.second < b.second; };
priority_queue<pair<char, int>, vector<pair<char, int>>, decltype(cmp)> q(cmp);
for (unordered_map<char, int>::iterator it = mp.begin(); it != mp.end(); ++it){
q.emplace(*it);
}
string res = "";
while (!q.empty()){
pair<char, int> p = q.top();
q.pop();
for (int i = 0; i < p.second; ++i){
res += p.first;
}
}
return res;
} |
思路桶排序 代码class Solution:
def frequencySort(self, s: str) -> str:
ret = []
countFrequency = collections.defaultdict(int)
for i in s:
countFrequency[i] += 1
buckets = [[] for _ in range(len(s) + 1)]
for i in countFrequency:
buckets[countFrequency[i]].extend(i*countFrequency[i])
for i in buckets[::-1]:
if(i):
ret.extend(i)
return ''.join(ret)复杂度时间:O(N) 空间:O(N) |
【Day 88】451 根据字符出现频率排序https://leetcode-cn.com/problems/sort-characters-by-frequency/comments/ 哈希解法 class Solution:
def frequencySort(self, s: str) -> str:
#哈希
d ={}
for i in s:
if i not in d:
d[i] = 0
d[i] += 1
sort1 = sorted(d,key= d.get,reverse=True)
res = ""
for k in sort1:
res += k*d[k]
return res复杂度分析： 时间复杂度：O(n+klogk) 空间复杂度：O（k） 堆的解法：
class Solution:
def frequencySort(self, s: str) -> str:
d= {}
for i in s:
d[i]= d.get(i,0)+1
items = [(-val,key) for key,val in d.items()]
heapq.heapify(items)
res = ""
while items:
val, key = heapq.heappop(items)
res += key*(-val)
return res时间复杂度：O(n+klogk) 空间复杂度：O（k） |
思路：堆排序时间复杂度：O（knlogk） |
Title:451. Sort Characters By FrequencyQuestion Reference LeetCodeSolutionHash table + heap. Codeclass Solution {
public:
void swap(pair<char,int>& a, pair<char, int>& b) {
char ch = a.first;
int cnt = a.second;
a.first = b.first;
a.second = b.second;
b.first = ch;
b.second = cnt;
}
void heap_push(std::vector<pair<char, int>> &heap, int& size, pair<char, int> val) {
heap[++size] = val;
int i = size;
while (i > 1 && heap[i].second > heap[i / 2].second) {
swap(heap[i], heap[i / 2]);
i /= 2;
}
}
int getBiggerChild(std::vector<pair<char, int>> &heap, int& size, int index) {
int l = index * 2;
int r = index * 2 + 1;
if (r > size || heap[l].second > heap[r].second)
return l;
return r;
}
pair<char, int> heap_pop(std::vector<pair<char, int>> &heap, int& size) {
pair<char, int> top = heap[1];
swap(heap[1], heap[size--]);
int i = 1;
while (i <= size / 2) {
int biggerChild = getBiggerChild(heap, size, i);
if (heap[i].second >= heap[biggerChild].second) {
break;
}
swap(heap[i], heap[biggerChild]);
i = biggerChild;
}
return top;
}
string frequencySort(string s) {
// Get the frequency of each character
std::map<char, int> counter;
for (char ch : s) {
counter[ch]++;
}
// Setup Heap
std::vector<pair<char, int>> heap(counter.size() + 1);
int size = 0;
// Initialize Heap.
for (auto it = counter.begin(); it != counter.end(); it++) {
heap_push(heap, size, make_pair(it->first, it->second));
}
// Generate result
string result;
while (size > 0) {
pair<char, int> top = heap_pop(heap, size);
result.append(string(top.second, top.first));
}
return result;
}
};
ComplexityTime Complexity and ExplanationO(n): used to put each letter into the hash table, after that, since we have the limited number of upper and lower letters, the time to put into heap takes O(1) Space Complexity and ExplanationO(1): we have 26 upper case letter, 26 lower case letter and 10 digits |
class Solution {
public String frequencySort(String s) {
int[] help = new int[123];
for (char c: s.toCharArray()) {
help[c]++;
}
PriorityQueue<int[]> queue = new PriorityQueue<>(122, (a, b) -> b[1] - a[1]);
for (int i = 0; i < 123; i++) {
if (help[i] > 0) {
queue.add(new int[]{i, help[i]});
}
}
StringBuilder sb = new StringBuilder();
int[] cur;
while (!queue.isEmpty()) {
cur = queue.poll();
for(int i = 0; i < cur[1]; i++) {
sb.append((char)cur[0]);
}
}
return sb.toString();
}
} |
代码
C++ Code: class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> mp;
int maxFreq = 0;
int length = s.size();
for (auto &ch : s) {
maxFreq = max(maxFreq, ++mp[ch]);
}
vector<string> buckets(maxFreq + 1);
for (auto &[ch, num] : mp) {
buckets[num].push_back(ch);
}
string ret;
for (int i = maxFreq; i > 0; i--) {
string &bucket = buckets[i];
for (auto &ch : bucket) {
for (int k = 0; k < i; k++) {
ret.push_back(ch);
}
}
}
return ret;
}
};
|
|
hashmap + sort class Solution:
def frequencySort(self, s: str) -> str:
hashmap = collections.defaultdict(int)
for char in s:
hashmap[char] += 1
sortedMap= sorted(hashmap.items(), key = lambda x: x[1], reverse = True)
res = ''
for key, val in sortedMap:
res += key * val
return res |
思路哈希表 代码class Solution:
def frequencySort(self, s):
li = []
for i, j in Counter(s).items():
li.append([i, j])
new_li = sorted(li, key=lambda x: -x[1])
return ''.join([i * j for i,j in new_li])复杂度
|
|
451. Sort Characters By FrequencyAlgoCodeclass Solution:
def frequencySort(self, s: str) -> str:
dict = {}
for ch in s: dict[ch] = dict.get(ch, 0) + 1
vals = sorted(dict.items(), key=lambda x : x[1], reverse=True)
res = ""
for k, v in vals: res += k * v
return resCompT: O(N+KlogK)S: O(K) |
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
heap = []
for i in lists:
while i:
heapq.heappush(heap,i.val)
i = i.next
d = c = ListNode(-1)
while heap:
c.next = ListNode(heapq.heappop(heap))
c = c.next
return d.next |
class Solution {
public String frequencySort(String s) {
int[] cc = new int[75];
Queue<int[]> queue = new PriorityQueue<>((a,b) -> b[0] - a[0] );
char[] c = s.toCharArray();
for(char ch : c) {
int ci = ch - '0';
cc[ci] ++;
}
for(int i = 0; i < 75 ; i ++) {
if(cc[i] != 0) {
queue.offer(new int[]{cc[i], i});
}
}
StringBuilder sb = new StringBuilder();
while(!queue.isEmpty()) {
int[] pair = queue.poll();
int ch = pair[0];
char cha = (char)('0' + pair[1]);
while(ch > 0) {
sb.append(cha);
ch --;
}
}
return sb.toString();
}
} |
Logic:Code:class Solution {
// plan 2
public String frequencySort(String s) {
StringBuilder sorted = new StringBuilder();
Map<Character, Integer> charFreqMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
charFreqMap.put(s.charAt(i), charFreqMap.getOrDefault(s.charAt(i), 0) + 1);
}
List<Character>[] charbuckets = new List[s.length() + 1];// index means freq, 0--s.length()
for (Map.Entry<Character, Integer> entry : charFreqMap.entrySet()) {
int freq = entry.getValue(); // index
if (charbuckets[freq] == null) {
charbuckets[freq] = new ArrayList<>();
}
charbuckets[freq].add(entry.getKey());
}
// traverse the buckets
for (int curFreq = s.length(); curFreq >= 0; curFreq--) {
if (charbuckets[curFreq] != null) {
for (char letter : charbuckets[curFreq]) {
for (int count = 0; count < curFreq; count++) {
sorted.append(letter);
}
}
}
}
return sorted.toString();
}
// plan 1
public String frequencySort1(String s) {
StringBuilder sorted = new StringBuilder();
Map<Character, Integer> charFreqMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
charFreqMap.put(s.charAt(i), charFreqMap.getOrDefault(s.charAt(i), 0) + 1);
}
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> (b.getValue() - a.getValue()));
maxHeap.addAll(charFreqMap.entrySet());
while (!maxHeap.isEmpty()) {
Map.Entry<Character, Integer> entry = maxHeap.poll();
for (int i = 0; i < entry.getValue(); i++) {
sorted.append(entry.getKey());
}
}
return sorted.toString();
}
} |
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
int frequency = map.getOrDefault(c, 0) + 1;
map.put(c, frequency);
}
List<Character> list = new ArrayList<Character>(map.keySet());
Collections.sort(list, (a, b) -> map.get(b) - map.get(a));
StringBuffer sb = new StringBuffer();
int size = list.size();
for (int i = 0; i < size; i++) {
char c = list.get(i);
int frequency = map.get(c);
for (int j = 0; j < frequency; j++) {
sb.append(c);
}
}
return sb.toString();
}
} |
Problemhttps://leetcode.com/problems/sort-characters-by-frequency/ Note
Solutionclass Solution {
public String frequencySort(String s) {
if(s == null || s.isEmpty()){
return s;
}
Map<Character, Integer> map = new HashMap<>();
PriorityQueue<Character> q = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
for(char c: s.toCharArray()){
map.put(c, map.getOrDefault(c, 0) + 1);
}
for(char c: map.keySet()){
q.offer(c);
}
StringBuilder sb = new StringBuilder();
while(!q.isEmpty()){
char c = q.poll();
for(int i = 0; i < map.get(c); i++){
sb.append(c);
}
}
return sb.toString();
}
}Complexity
|
思路
代码javascript /*
* @lc app=leetcode.cn id=451 lang=javascript
*
* [451] 根据字符出现频率排序
*/
// @lc code=start
/**
* @param {string} s
* @return {string}
*/
var frequencySort = function(s) {
const map = {}
for (let i = 0; i < s.length; i++) {
const char = s[i]
map[char] = map[char] || 0
map[char]++
}
const mapKeys = Object.keys(map)
mapKeys.sort((a, b) => map[b] - map[a])
let str = ''
for (let i = 0; i < mapKeys.length; i++) {
const char = mapKeys[i]
const subStr = char.repeat(map[char])
str += subStr
}
return str
};
// @lc code=end复杂度分析
|
思路hashmap + sort 代码class Solution:
def frequencySort(self, s: str) -> str:
d = {}
for chara in s:
d[chara] = d.get(chara, 0) + 1
new = list(d.items())
sort_new = sorted(new, key = lambda x:x[1], reverse = True)
result = ""
for i in range(len(sort_new)):
result += (sort_new[i][0] * sort_new[i][1])
return result复杂度分析时间复杂度：O(nlogn) |
|
思路 实现语言: C++
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> dict;
for (auto& ch : s)
{
if (dict.find(ch) == dict.end())
dict[ch] = 1;
else dict[ch]++;
}
string res;
vector<pair<char, int>> kvVect;
for (auto& kvp : dict)
kvVect.push_back(kvp);
auto cmp = [](const pair<char, int>& p1, const pair<char, int>& p2)
{
return p1.second > p2.second;
};
sort(kvVect.begin(), kvVect.end(), cmp);
for (auto& kvp : kvVect)
{
while (kvp.second--)
res.push_back(kvp.first);
}
return res;
}
};复杂度分析 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
451 根据字符出现频率排序
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/sort-characters-by-frequency/comments/
前置知识
题目描述
The text was updated successfully, but these errors were encountered: