451. 根据字符出现频率排序-字符映射法+快速排序
2023-09-14 09:06:49 时间
451. 根据字符出现频率排序-字符映射法+快速排序
给定一个字符串 s ,根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案,返回其中任何一个。
示例 1:
输入: s = “tree”
输出: “eert”
解释: 'e’出现两次,'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外,"eetr"也是一个有效的答案。
示例 2:
输入: s = “cccaaa”
输出: “cccaaa”
解释: 'c’和’a’都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
示例 3:
输入: s = “Aabb”
输出: “bbAa”
解释: 此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意’A’和’a’被认为是两种不同的字符。
这题还是不错的一个题目,感兴趣学习一下,解题代码如下:
void quick_sort(int **nums,int low,int high){
if(low<high){
int *a=(int *)malloc(sizeof(int)*2);
int p=nums[low][0],l=low,h=high;
int p1=nums[low][1];
a[0]=p;
a[1]=p1;
while(low<high){
while(low<high&&nums[high][1]<=p1){
high--;
}
nums[low][0]=nums[high][0];
nums[low][1]=nums[high][1];
while(low<high&&nums[low][1]>=p1){
low++;
}
nums[high][0]=nums[low][0];
nums[high][1]=nums[low][1];
}
nums[low][0]=p;
nums[low][1]=p1;
quick_sort(nums,l,low-1);
quick_sort(nums,low+1,h);
}
}
char * frequencySort(char * s){
int r[129];
int **a=(int **)malloc(sizeof(int *)*129);
for(int i=0;i<129;i++){
a[i]=(int *)malloc(sizeof(int )*2);
a[i][0]=i;
a[i][1]=0;
r[i]=0;
}
for(int i=0;s[i]!='\0';i++){
r[s[i]]++;
}
for(int i=0;i<129;i++){
a[i][1]=r[i];
//printf("|%d %d ",a[i][0],a[i][1]);
}
quick_sort(a,0,128);
int size=0;
for(int i=0;i<129;i++){
// a[i][1]=r[i];
for(int j=0;j<a[i][1];j++){
s[size++]=a[i][0];
}
// printf("|%d %d ",a[i][0],a[i][1]);
}
return s;
}
相关文章
- Java实现 LeetCode 451 根据字符出现频率排序
- Java实现 LeetCode 451 根据字符出现频率排序
- Java实现 LeetCode 395 至少有K个重复字符的最长子串
- python 修改字符串中的某一位字符
- 最长回文字符(需要补)
- javascrpt插入html中中文字符乱码问题记录
- PHP 一般字符《=》16 // 2进制
- 根据字符出现频率排序
- C/C++基础讲解(七十七)之常见试题解答篇(同时整除/字符左右排序)
- C++中三种风格的字符表示法
- VB编程:统计字符个数-52_彭世瑜_新浪博客
- 【Android 逆向】Linux 文件分类 ( 普通文件 | 目录文件 | 链接文件 | 字符设备文件 | 管道文件 | 块设备文件 )
- EditText限制输入字符类型的几种方式
- Python制作字符画(pillow,numpy的使用)