当前位置:网站首页>LeetCode 1636. Sort the array in ascending order by frequency
LeetCode 1636. Sort the array in ascending order by frequency
2022-07-06 16:43:00 【Daylight629】
1636. Sort the array in ascending order by frequency
Give you an array of integers nums
, Please arrange the array according to the frequency of each value Ascending Sort . If there are multiple values with the same frequency , Please put them according to the value itself Descending Sort .
Please return the sorted array .
Example 1:
Input :nums = [1,1,2,2,2,3]
Output :[3,1,1,2,2,2]
explain :'3' The frequency is 1,'1' The frequency is 2,'2' The frequency is 3 .
Example 2:
Input :nums = [2,3,1,3,2]
Output :[1,3,3,2,2]
explain :'2' and '3' The frequencies are 2 , So they are sorted in descending order according to the value itself .
Example 3:
Input :nums = [-1,1,-6,4,5,-6,1,4,1]
Output :[5,-1,4,4,-6,-6,1,1,1]
Tips :
1 <= nums.length <= 100
-100 <= nums[i] <= 100
Two 、 Method 1
Hash + Priority queue
class Solution {
public int[] frequencySort(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2)
-> o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]
);
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
queue.add(new int[]{
entry.getValue(), entry.getKey()});
}
int[] res = new int[nums.length];
int idx = 0;
while (!queue.isEmpty()) {
int[] pos = queue.poll();
for (int i = 0; i< pos[0]; i++) {
res[idx++] = pos[1];
}
}
return res;
}
}
Complexity analysis
Time complexity :O(n).
Spatial complexity :O(n).
边栏推荐
- 875. Leetcode, a banana lover
- Research Report on market supply and demand and strategy of China's four seasons tent industry
- antd upload beforeUpload中禁止触发onchange
- Tert butyl hydroquinone (TBHQ) Industry Research Report - market status analysis and development prospect forecast
- Log statistics (double pointer)
- Native JS realizes the functions of all selection and inverse selection -- Feng Hao's blog
- Detailed explanation of FLV format
- 本地可视化工具连接阿里云centOS服务器的redis
- Problem - 922D、Robot Vacuum Cleaner - Codeforces
- 第五章 Yarn资源调度器
猜你喜欢
第三章 MapReduce框架原理
LeetCode 1560. The sector with the most passes on the circular track
SF smart logistics Campus Technology Challenge (no T4)
QT realizes window topping, topping state switching, and multi window topping priority relationship
Codeforces Round #802(Div. 2)A~D
Li Kou: the 81st biweekly match
Chapter 2 shell operation of hfds
Kubernetes集群部署
QT implementation fillet window
Problem - 922D、Robot Vacuum Cleaner - Codeforces
随机推荐
QT simulates mouse events and realizes clicking, double clicking, moving and dragging
Spark independent cluster dynamic online and offline worker node
Kubernetes cluster deployment
Bidirectional linked list - all operations
Log statistics (double pointer)
(lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
Simple records of business system migration from Oracle to opengauss database
第7章 __consumer_offsets topic
第6章 DataNode
解决Intel12代酷睿CPU单线程只给小核运行的问题
Hbuilder X格式化快捷键设置
业务系统从Oracle迁移到openGauss数据库的简单记录
Solve the problem of intel12 generation core CPU [small core full, large core onlookers] (win11)
Click QT button to switch qlineedit focus (including code)
The concept of spark independent cluster worker and executor
Research Report on market supply and demand and strategy of Chinese table lamp industry
CMake Error: Could not create named generator Visual Studio 16 2019解决方法
JS time function Daquan detailed explanation ----- AHAO blog
Basic principles of video compression coding and audio compression coding
字节跳动新程序员成长秘诀:那些闪闪发光的宝藏mentor们