Array
Hash Table
Sorting
Description
Given an array of integers nums
, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.
Return the sorted array .
Example 1:
Input: nums = [1,1,2,2,2,3]
Output: [3,1,1,2,2,2]
Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3.
Example 2:
Input: nums = [2,3,1,3,2]
Output: [1,3,3,2,2]
Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order.
Example 3:
Input: nums = [-1,1,-6,4,5,-6,1,4,1]
Output: [5,-1,4,4,-6,-6,1,1,1]
Constraints:
1 <= nums.length <= 100
-100 <= nums[i] <= 100
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust JavaScript
class Solution :
def frequencySort ( self , nums : List [ int ]) -> List [ int ]:
cnt = Counter ( nums )
return sorted ( nums , key = lambda x : ( cnt [ x ], - x ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public int [] frequencySort ( int [] nums ) {
int [] cnt = new int [ 201 ] ;
List < Integer > t = new ArrayList <> ();
for ( int v : nums ) {
v += 100 ;
++ cnt [ v ] ;
t . add ( v );
}
t . sort (( a , b ) -> cnt [ a ] == cnt [ b ] ? b - a : cnt [ a ] - cnt [ b ] );
int [] ans = new int [ nums . length ] ;
int i = 0 ;
for ( int v : t ) {
ans [ i ++] = v - 100 ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public :
vector < int > frequencySort ( vector < int >& nums ) {
vector < int > cnt ( 201 );
for ( int v : nums ) {
++ cnt [ v + 100 ];
}
sort ( nums . begin (), nums . end (), [ & ]( const int a , const int b ) {
if ( cnt [ a + 100 ] == cnt [ b + 100 ]) return a > b ;
return cnt [ a + 100 ] < cnt [ b + 100 ];
});
return nums ;
}
};
func frequencySort ( nums [] int ) [] int {
cnt := make ([] int , 201 )
for _ , v := range nums {
cnt [ v + 100 ] ++
}
sort . Slice ( nums , func ( i , j int ) bool {
a , b := nums [ i ] + 100 , nums [ j ] + 100
return cnt [ a ] < cnt [ b ] || cnt [ a ] == cnt [ b ] && a > b
})
return nums
}
function frequencySort ( nums : number []) : number [] {
const map = new Map < number , number > ();
for ( const num of nums ) {
map . set ( num , ( map . get ( num ) ?? 0 ) + 1 );
}
return nums . sort (( a , b ) => map . get ( a ) - map . get ( b ) || b - a );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 use std :: collections :: HashMap ;
impl Solution {
pub fn frequency_sort ( mut nums : Vec < i32 > ) -> Vec < i32 > {
let n = nums . len ();
let mut map = HashMap :: new ();
for & num in nums . iter () {
* map . entry ( num ). or_insert ( 0 ) += 1 ;
}
nums . sort_by ( | a , b | {
if map . get ( a ) == map . get ( b ) {
return b . cmp ( a );
}
map . get ( a ). cmp ( & map . get ( b ))
});
nums
}
}
1
2
3
4
5
6
7
8
9
10
11
12 /**
* @param {number[]} nums
* @return {number[]}
*/
var frequencySort = function ( nums ) {
const m = new Map ();
for ( let i = 0 ; i < nums . length ; i ++ ) {
m . set ( nums [ i ], ( m . get ( nums [ i ]) || 0 ) + 1 );
}
nums . sort (( a , b ) => ( m . get ( a ) != m . get ( b ) ? m . get ( a ) - m . get ( b ) : b - a ));
return nums ;
};