【力扣 leetcode】1636：按照频率将数组升序排列

骑猪看日落 2023-10-09 14:45 5阅读 0赞

## 每日进步 ##

这道题比较简单，刚好可以练习“leetcode850：矩形面积II”中出现的部分数据结构和代码思路。

*  **列表：** `List<int[]> list = new ArrayList<int[]>();`
 *  **排序：** `Collections.sort(list, 比较器)`
    
     *  比较器返回值大于0时交换前后元素，比较器返回值小于0时不交换。

## 题目 ##

给你一个整数数组`nums`，请你将数组按照每个值的频率**升序**排序。如果有多个值的频率相同，请你按照数值本身将它们**降序**排序。  
请你返回排序后的数组。

*  **示例1：**
    
     *  **输入：** `nums = [1,1,2,2,2,3]`
     *  **输出：** `[3,1,1,2,2,2]`
     *  **解释：** ‘3’ 频率为 1，‘1’ 频率为 2，‘2’ 频率为 3 。
 *  **示例2：**
    
     *  **输入：** `nums = [2,3,1,3,2]`
     *  **输出：** `[1,3,3,2,2]`
     *  **解释：** ‘2’ 和 ‘3’ 频率都为 2 ，所以它们之间按照数值本身降序排序。
 *  **示例3：**
    
     *  **输入：** `nums = [-1,1,-6,4,5,-6,1,4,1]`
     *  **输出：** `[5,-1,4,4,-6,-6,1,1,1]`
 *  **提示：**
    
     *  `1 <= nums.length <= 100`
     *  `-100 <= nums[i] <= 100`

> 来源：力扣（LeetCode）  
> 链接：https://leetcode.cn/problems/sort-array-by-increasing-frequency  
> 著作权归领扣网络所有。本文仅供个人学习，非商用。

## 题解 ##

**暴力求解：**

*  首先，我们将数组按大小排序，以便后续统计出现频率。
 *  然后，我们将各元素及其出现频率以“（元素，频率）”的形式储存到一个列表中。
 *  其次，对列表进行排序。排序规则为：优先按频率升序排列，频率相同时按元素大小降序排列。
 *  最后，我们遍历列表，按照顺序和出现次数将元素移动到数组中。

class Solution {
        
        public int[] frequencySort(int[] nums) {
        
            Arrays.sort(nums);
            List<int[]> list = new ArrayList<int[]>();
    
            for (int i = 0; i < nums.length; i++){
        
                int j = i;
                while (j < nums.length-1 && nums[j+1] == nums[i]){
        
                    j++;
                }
                int times = j - i + 1;
                list.add(new int[]{
        nums[i], times});
                i = j;
            }
    
            Collections.sort(list, (a, b) ->{
        
                if (a[1] == b[1])
                    return b[0] - a[0];
                else
                    return a[1] - b[1];
            });
    
            int[] ans = new int[nums.length];
            for (int i=0, k=0; i < list.size(); i++){
        
                int[] arr = list.get(i);
                for (int j = 0; j < arr[1]; j++, k++){
        
                    ans[k] = arr[0];
                }
            }
            return ans;
        }
    }