FilesExpand file tree

 master

/

SortCharactersByFrequency_451.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

73 lines (70 loc) · 2.16 KB

 master

/

SortCharactersByFrequency_451.java

Copy path

Top

File metadata and controls

• Code
• Blame

73 lines (70 loc) · 2.16 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

66

67

68

69

70

71

72

73

package HashTable;

import java.util.*;

/**

* 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

*/

public class SortCharactersByFrequency_451 {

public static String frequencySortFaster(String s) {

//统计频率，使用频率进行排序

int[] freq=new int[128];

char[] array = s.toCharArray();

for(char c:array){

freq[c]++;

}

PriorityQueue<Character> pq=new PriorityQueue<>((a,b)->Integer.compare(freq[b],freq[a]));

for(int i=0;i<freq.length;i++){

if(freq[i]!=0){

pq.offer((char)i);

}

}

StringBuilder stringBuilder=new StringBuilder();

while (!pq.isEmpty()){

Character c = pq.poll();

while (freq[c]-- > 0){

stringBuilder.append(c);

}

}

return stringBuilder.toString();

}

public static String frequencySort(String s) {

//写的太麻烦

if(s==null||s.length()==0) {

return "";

}

char[] charArray = s.toCharArray();

Arrays.sort(charArray);

PriorityQueue<int[]> pq=new PriorityQueue<>(new Comparator<int[]>() {

@Override

public int compare(int[] o1, int[] o2) {

return o2[1]-o1[1];

}

});

int begin=0;

char c=charArray[0];

int end=0;

//[start,end)

for(int i=0;i<charArray.length;i++){

if(charArray[i]==c){

end++;

}else{

pq.add(new int[]{begin,end-begin});

end=i+1;

begin=i;

c=charArray[i];

}

}

pq.add(new int[]{begin,end-begin});

StringBuilder stringBuilder=new StringBuilder();

while (!pq.isEmpty()){

int[] poll = pq.poll();

for(int freq=0;freq<poll[1];freq++){

stringBuilder.append(charArray[poll[0]]);

}

}

return stringBuilder.toString();

}

public static void main(String[] args) {

String tree = frequencySortFaster("tree");

System.out.println(tree);

}

}