Daily LeetCode – day0052 1636. Sort Array by Increasing Frequency

import java.util.*;

// 1636. Sort Array by Increasing Frequency
class Solution {
    public int[] frequencySort(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            if (hashMap.containsKey(num)) {
                hashMap.put(num, hashMap.get(num) + 1);
            } else {
                hashMap.put(num, 1);
            }
        }
        TreeSet<Pair> treeSet = new TreeSet<>();
        for (Map.Entry<Integer, Integer> e : hashMap.entrySet()) {
            treeSet.add(new Pair(e.getKey(), e.getValue()));
        }
        int[] ans = new int[nums.length];
        int i = 0;
        for (Pair p : treeSet) {
            for (int j = 0; j < p.frequency; ++j) {
                ans[i] = p.value;
                ++i;
            }
        }
        return ans;
    }
}

class Pair implements Comparable<Pair> {
    int value;
    int frequency;

    public Pair(int value, int frequency) {
        this.value = value;
        this.frequency = frequency;
    }

    @Override
    public int compareTo(Pair o) {
        if (frequency == o.frequency) return o.value - value;
        return frequency - o.frequency;
    }
}
学习笔记:
这就是一道经典的自定义排序题,还用到了hashmap特别考验扎实基本功。
先要按照频率从少到多排,相同数字再从大到小排。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。