Leetcode --- Sort Characters By Frequency
===

## Description

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

給一個字串,重組他的排序,排序方法為出現越多次的字元排在最前面

### Examples

* Ex1:
**Input**: s = "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.

* Ex2:
**Input**: s = "cccaaa"
**Output**: "aaaccc"
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.

* Ex3:
**Input**: s = "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.

### Constraints

* 1 <= s.length <= 5 * 10^5^
* s consists of English letters and digits.(a...z,A...Z,0...9)

## Solution

==Bucket sort:==

First of all,we allocate an array,which be named map,for saving the number of each appeared characters,and creat another array,which be named rank,for saving its rank order.

The second step is maintaining the rank order in rank when the number of appeared characters was growing in for loop.

Consequently,according to the rank can knew how the character order in the answer's string,and the required number of repetitions for each character had been stored in map.

### Implentment code

import java.util.*;
class Solution {
    public String frequencySort(String s) {
    
        if(s.length() < 3 )
            return s;
        int[] map = new int[256];
        Character[] rank = new Character[256];
        int rank_tail =0;

        for(char ch : s.toCharArray())
        {
            map[ch]++;
            int pos = Arrays.asList(rank).indexOf(ch);
            if(pos == -1)
            {
                rank[rank_tail] = ch;
                rank_tail++;
                continue;
            }
            while(pos > 0 && map[rank[pos]] > map[rank[pos-1]])
            {
                char tmp = rank[pos-1];
                rank[pos-1] = rank[pos];
                rank[pos] = tmp;
                pos--;
            }
        }
        
        StringBuilder ans =new StringBuilder();
        for(int i =0;i<rank_tail;i++)
        {
            for(int j =0;j<map[rank[i]];j++)
            {
                ans.append(rank[i]);
            }
        }
        return ans.toString();
    }
}

map陣列 : map[字元] = 次數
rank陣列 : rank[排名] = 字元

line 5 : 最不重要也最為重要的一行,加速的關鍵,把邊界條件做加速,22ms -> 14ms
line 12 :用作查詢array中是否有這個value,有則回傳其index,否則回-1
line 13~18 : 當字元第一次近來時的初始化
line 19 ~25 : 當排名發生變化時交換排名,因為相同數量會有相同排名的問題,所以要往上交換直到正確排名

#### Submissions on Leetcode

Runtime: **14 ms, faster than 57.32%** of Java online submissions for Sort Characters By Frequency.
Memory Usage: **40.1 MB, less than 46.60%** of Java online submissions for Sort Characters By Frequency.

#### Time complexity

最差狀況發生在input為全部字元都不一樣而且最後兩個為一樣,會在交換排名時因為前面排名全部都相同導致要一路從最後一個爬到第一個
但最多也只有26+26+10 = 52個不同字元 ,而輸入最多為 5 * 10^5^ ,所以可以被忽略
**=> O(n) , n = s.length()**

## Conclusion
一個很好練習bucket sort 的題目 , 在分堆部分可以使用array,hashmap..不同結構完成

###### tags: `Leetcode` `Medium` `String` `Sort`