按字符的频率对字符串排序

题目：

给定一个字符串，根据字符的频率按递减顺序对其进行排序。

示例：

按字符的频率对字符串排序

思路：这个过程其实就是统计字符串中某个字符的个数，然后对这些个数进行排序，依次从大到小的输出指定个数的字符。如果稍微忽略空间的影响，则可以创建s.length个数的list集合，每一个集合分别表示元素的个数，例如标号为1的集合表示该集合里的元素个数都是1，依次类推，所以元素最多也就是s.length个，也就是全部都是一个元素。但是另外一个问题就是怎么知道某个字符的个数是多少咧，如果使用map的话，可以存储字符以及相应的个数，但是最后不容易遍历，所以可以换另外一种方法，使用一个一维数组来存储字符和其对应的个数，数组的下标表示字符（使用字符的code值），元素值表示该字符的个数，这样就需要一个大小为256的数组。通过这个数组记录元素以及元素的个数，然后转换为一个二维的list来输出所有的值。

代码：

class Solution {
    public String frequencySort(String s) {
    char []a=s.toCharArray();
		int []count=new int [256];
		StringBuilder stringBuilder=new StringBuilder();
		List<List<Integer>> list=new ArrayList<>();
		//依次遍历字符串，count数组中的元素表示第n个字符出现的个数，n表示字符的code值
		for(int i=0;i<s.length();i++)
		{
			count[s.charAt(i)]++;
			list.add(new ArrayList<Integer>());
		}
		//要多加一个list，可能所有的字符全为一个元素，则元素的总个数为s.length,而list最后一个表示的是length-1的值
		list.add(new ArrayList<Integer>());
		//依次将出现次数的字符加入list中
		//比如字符a出现了一次，则加入编号为1的list中，b也是出现一次，同样加入编号为1的list中
		for(int i=0;i<count.length;i++)
		{
			if(count[i]!=0)
				list.get(count[i]).add(i);
		}
		//这样字符以及个数就转换为一个二级list
		//接下来就是一次遍历字符,从最后一个字符开始遍历
		for(int i=list.size()-1;i>0;i--)
		{
			if(list.get(i)!=null)
			{
				//将list中的集合取出来，再依次遍历
				List<Integer> word=list.get(i);
				for(int j=0;j<word.size();j++)
				{
					for(int k=0;k<i;k++)
					{
						stringBuilder.append(Character.toChars(word.get(j)));
					}
				}
			}
		}
		
		
		
		
		
		return stringBuilder.toString();
}}

代码中也有很详细的思路。

按字符的频率对字符串排序

相关推荐