451. Sort Characters By Frequency

451. Sort Characters By Frequency
먼저 횟수 를 통계 한 다음 에 횟수 에 따라 새로운 string 을 구성한다.생각 하 는 것 이 그리 어렵 지 않 아서 쓰기 에는 아직 좀 번거롭다.priority quue 를 사 용 했 습 니 다.

    class Wrapper {
        public char c;
        public int freq;

        public Wrapper(char c, int freq) {
            this.c = c;
            this.freq = freq;
        }
    }

    public String frequencySort(String s) {
        if (s==null || s.length() == 0) return "";
        Map map = new HashMap<>();
        Set set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            int count = map.getOrDefault(s.charAt(i), 0);
            map.put(s.charAt(i), ++count);
            set.add(s.charAt(i));
        }
        PriorityQueue pq = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Wrapper o1, Wrapper o2) {
                return o1.freq - o2.freq;
            }
        });
        for (char c : set) {
            pq.offer(new Wrapper(c, map.get(c)));
        }
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Wrapper w = pq.poll();
            for (int i = 0; i < w.freq; i++) {
                sb.insert(0, w.c);
            }
        }
        return sb.toString();
    }

Priority Queue 를 사 용 했 기 때문에 복잡 도 는 O (nlogn) 입 니 다.다른 사람의 답 을 보 니 O (n) 인 것 이 있 고 배열 의 index 로 나타 난 횟수 를 표시 했다.그리고 저 는 hashset 을 사 용 했 습 니 다. hashmap 의 옮 겨 다 니 는 것 을 잘 모 르 기 때문에 아래 코드 도 hashmap 의 옮 겨 다 니 는 방법 을 보 여 주 었 습 니 다. for (char c: map. keyset ():

public String frequencySort(String s) {
    if (s == null) {
        return null;
    }
    Map map = new HashMap();
    char[] charArray = s.toCharArray();
    int max = 0;
    for (Character c : charArray) {
        if (!map.containsKey(c)) {
            map.put(c, 0);
        }
        map.put(c, map.get(c) + 1);
        max = Math.max(max, map.get(c));
    }

    List[] array = buildArray(map, max);

    return buildString(array);
}

private List[] buildArray(Map map, int maxCount) {
    List[] array = new List[maxCount + 1];
    for (Character c : map.keySet()) {
        int count = map.get(c);
        if (array[count] == null) {
            array[count] = new ArrayList();
        }
        array[count].add(c);
    }
    return array;
}

private String buildString(List[] array) {
    StringBuilder sb = new StringBuilder();
    for (int i = array.length - 1; i > 0; i--) {
        List list = array[i];
        if (list != null) {
            for (Character c : list) {
                for (int j = 0; j < i; j++) {
                    sb.append(c);
                }
            }
        }
    }
    return sb.toString();
}