1122. Relative Sort Array
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 inarr1
.
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.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Solution 2: Counting Sort
We can use the idea of counting sort. First, count the occurrence of each element in array $arr1$. Then, according to the order in array $arr2$, put the elements in $arr1$ into the answer array $ans$ according to their occurrence. Finally, we traverse all elements in $arr1$ and put the elements that do not appear in $arr2$ in ascending order at the end of the answer array $ans$.
The time complexity is $O(n + m)$, and the space complexity is $O(n)$. Where $n$ and $m$ are the lengths of arrays $arr1$ and $arr2$ respectively.
Python3
class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
cnt = Counter(arr1)
ans = []
for x in arr2:
ans.extend([x] * cnt[x])
cnt.pop(x)
mi, mx = min(arr1), max(arr1)
for x in range(mi, mx + 1):
ans.extend([x] * cnt[x])
return ans
Java
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] cnt = new int[1001];
int mi = 1001, mx = 0;
for (int x : arr1) {
++cnt[x];
mi = Math.min(mi, x);
mx = Math.max(mx, x);
}
int m = arr1.length;
int[] ans = new int[m];
int i = 0;
for (int x : arr2) {
while (cnt[x] > 0) {
--cnt[x];
ans[i++] = x;
}
}
for (int x = mi; x <= mx; ++x) {
while (cnt[x] > 0) {
--cnt[x];
ans[i++] = x;
}
}
return ans;
}
}
C++
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<int> cnt(1001);
for (int x : arr1) {
++cnt[x];
}
auto [mi, mx] = minmax_element(arr1.begin(), arr1.end());
vector<int> ans;
for (int x : arr2) {
while (cnt[x]) {
ans.push_back(x);
--cnt[x];
}
}
for (int x = *mi; x <= *mx; ++x) {
while (cnt[x]) {
ans.push_back(x);
--cnt[x];
}
}
return ans;
}
};
Go
func relativeSortArray(arr1 []int, arr2 []int) []int {
cnt := make([]int, 1001)
mi, mx := 1001, 0
for _, x := range arr1 {
cnt[x]++
mi = min(mi, x)
mx = max(mx, x)
}
ans := make([]int, 0, len(arr1))
for _, x := range arr2 {
for cnt[x] > 0 {
ans = append(ans, x)
cnt[x]--
}
}
for x := mi; x <= mx; x++ {
for cnt[x] > 0 {
ans = append(ans, x)
cnt[x]--
}
}
return ans
}
TypeScript
function relativeSortArray(arr1: number[], arr2: number[]): number[] {
const cnt = Array(1001).fill(0);
let mi = Number.POSITIVE_INFINITY;
let mx = Number.NEGATIVE_INFINITY;
for (const x of arr1) {
cnt[x]++;
mi = Math.min(mi, x);
mx = Math.max(mx, x);
}
const ans: number[] = [];
for (const x of arr2) {
while (cnt[x]) {
cnt[x]--;
ans.push(x);
}
}
for (let i = mi; i <= mx; i++) {
while (cnt[i]) {
cnt[i]--;
ans.push(i);
}
}
return ans;
}
Swift
class Solution {
func relativeSortArray(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
var cnt = [Int](repeating: 0, count: 1001)
for x in arr1 {
cnt[x] += 1
}
guard let mi = arr1.min(), let mx = arr1.max() else {
return []
}
var ans = [Int]()
for x in arr2 {
while cnt[x] > 0 {
ans.append(x)
cnt[x] -= 1
}
}
for x in mi...mx {
while cnt[x] > 0 {
ans.append(x)
cnt[x] -= 1
}
}
return ans
}
}