Leetcode[451] Sort Characters By Frequency Medium

86 阅读 0 评论 57 点赞

我是靠谱客的博主善良小松鼠，这篇文章主要介绍Leetcode[451] Sort Characters By Frequency Medium，现在分享给大家，希望可以做个参考。

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
“tree”

Output:
“eert”

Explanation:
‘e’ appears twice while ‘r’ and ‘t’ both appear once.
So ‘e’ must appear before both ‘r’ and ‘t’. Therefore “eetr” is also a valid answer.
Example 2:

Input:
“cccaaa”

Output:
“cccaaa”

Explanation:
Both ‘c’ and ‘a’ appear three times, so “aaaccc” is also a valid answer.
Note that “cacaca” is incorrect, as the same characters must be together.
Example 3:

Input:
“Aabb”

Output:
“bbAa”

Explanation:
“bbaA” is also a valid answer, but “Aabb” is incorrect.
Note that ‘A’ and ‘a’ are treated as two different characters.

类似的题，按数组中出现频次大小排序

http://www.geeksforgeeks.org/amazon-interview-set-21/

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>

typedef struct
{
	int id;
	int count;
}item;

void sort(int a[], int n)
{
	item temp[n];
	memset(temp,0,sizeof(temp));
	
	int index=0;
	for(int i=0;i<n;i++)
	{
		int count=1;
		temp[index].id=a[i];
		while(temp[index].id==a[i+count])
		{
			count++;
		}
		temp[index].count=count;
		printf("id:%d,count:%dn",temp[index].id,temp[index].count);
		index++;
		i+=count-1;
	}

	int j=0;
	int k=0;
	while(temp[j].count!=0) //should usd stable sort
	{
		int k=j+1;
		while(temp[k].count!=0)
		{
			if(temp[k].count>temp[j].count)
			{
				item var=temp[j];
				temp[j]=temp[k];
				temp[k]=var;
			}
			k+=1;
		}
		printf("id:%d,count:%dn",temp[j].id,temp[j].count);
		j+=1;
	}
	printf("dddddn");
	int m=0;
	while(temp[m].count!=0)
	{
		while(temp[m].count--)
		{
			printf("%d",temp[m].id);
		}
		m+=1;
	}
}
int main(void)
{
	// your code goes here
	int a[]={65,65,1,1,1,2,2,0,9,9,9,9};
	sort(a,12);
	return 0;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def frequencySort(self, s):
        """
        :type s: str
        :rtype: str
        """
        s_set = set(s)
        table = []
        for val in s_set:
            table.append((val, s.count(val)))

        table.sort(key = lambda x: x[1], reverse = True) 

        return ''.join(map(lambda x: x[0] * x[1], table))