Array
Hash Table
Counting Sort
Sorting
Description
Given two arrays arr1
and arr2
, the elements of arr2
are distinct, and all elements in arr2
are also in arr1
.
Sort the elements of arr1
such that the relative ordering of items in arr1
are the same as in arr2
. Elements that do not appear in arr2
should be placed at the end of arr1
in ascending order.
Example 1:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]
Example 2:
Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]
Constraints:
1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
All the elements of arr2
are distinct .
Each arr2[i]
is in arr1
.
Solutions
Solution 1: Custom Sorting
First, we use a hash table $pos$ to record the position of each element in array $arr2$. Then, we map each element in array $arr1$ to a tuple $(pos.get(x, 1000 + x), x)$, and sort these tuples. Finally, we take out the second element of all tuples and return it.
The time complexity is $O(n \times \log n + m)$, and the space complexity is $O(n + m)$. Here, $n$ and $m$ are the lengths of arrays $arr1$ and $arr2$, respectively.
Python3 Java C++ Go TypeScript
class Solution :
def relativeSortArray ( self , arr1 : List [ int ], arr2 : List [ int ]) -> List [ int ]:
pos = { x : i for i , x in enumerate ( arr2 )}
return sorted ( arr1 , key = lambda x : pos . get ( x , 1000 + x ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public int [] relativeSortArray ( int [] arr1 , int [] arr2 ) {
Map < Integer , Integer > pos = new HashMap <> ( arr2 . length );
for ( int i = 0 ; i < arr2 . length ; ++ i ) {
pos . put ( arr2 [ i ] , i );
}
int [][] arr = new int [ arr1 . length ][ 0 ] ;
for ( int i = 0 ; i < arr . length ; ++ i ) {
arr [ i ] = new int [] { arr1 [ i ] , pos . getOrDefault ( arr1 [ i ] , arr2 . length + arr1 [ i ] )};
}
Arrays . sort ( arr , ( a , b ) -> a [ 1 ] - b [ 1 ] );
for ( int i = 0 ; i < arr . length ; ++ i ) {
arr1 [ i ] = arr [ i ][ 0 ] ;
}
return arr1 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
vector < int > relativeSortArray ( vector < int >& arr1 , vector < int >& arr2 ) {
unordered_map < int , int > pos ;
for ( int i = 0 ; i < arr2 . size (); ++ i ) {
pos [ arr2 [ i ]] = i ;
}
vector < pair < int , int >> arr ;
for ( int i = 0 ; i < arr1 . size (); ++ i ) {
int j = pos . count ( arr1 [ i ]) ? pos [ arr1 [ i ]] : arr2 . size ();
arr . emplace_back ( j , arr1 [ i ]);
}
sort ( arr . begin (), arr . end ());
for ( int i = 0 ; i < arr1 . size (); ++ i ) {
arr1 [ i ] = arr [ i ]. second ;
}
return arr1 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 func relativeSortArray ( arr1 [] int , arr2 [] int ) [] int {
pos := map [ int ] int {}
for i , x := range arr2 {
pos [ x ] = i
}
arr := make ([][ 2 ] int , len ( arr1 ))
for i , x := range arr1 {
if p , ok := pos [ x ]; ok {
arr [ i ] = [ 2 ] int { p , x }
} else {
arr [ i ] = [ 2 ] int { len ( arr2 ), x }
}
}
sort . Slice ( arr , func ( i , j int ) bool {
return arr [ i ][ 0 ] < arr [ j ][ 0 ] || arr [ i ][ 0 ] == arr [ j ][ 0 ] && arr [ i ][ 1 ] < arr [ j ][ 1 ]
})
for i , x := range arr {
arr1 [ i ] = x [ 1 ]
}
return arr1
}
1
2
3
4
5
6
7
8
9
10
11
12
13 function relativeSortArray ( arr1 : number [], arr2 : number []) : number [] {
const pos : Map < number , number > = new Map ();
for ( let i = 0 ; i < arr2 . length ; ++ i ) {
pos . set ( arr2 [ i ], i );
}
const arr : number [][] = [];
for ( const x of arr1 ) {
const j = pos . get ( x ) ?? arr2 . length ;
arr . push ([ j , x ]);
}
arr . sort (( a , b ) => a [ 0 ] - b [ 0 ] || a [ 1 ] - b [ 1 ]);
return arr . map ( a => a [ 1 ]);
}
GitHub