问题描述
给你两个数组，arr1 和 arr2，
arr2 中的元素各不相同arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
1 <= arr1.length, arr2.length <= 10000 <= arr1[i], arr2[i] <= 1000arr2 中的元素 arr2[i] 各不相同arr2 中的每个元素 arr2[i] 都出现在 arr1 中
解题思路
常规做法就是先记录 \(arr1\) 中的每个元素出现的次数，然后再按照在 \(arr2\) 中的顺序将这些元素放入一个数组，最后对 \(arr1\) 中不在 \(arr2\) 中的元素排序，最后返回两个数组排列的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
count = {}
for x in arr1:
count[x] = count.get(x, 0) + 1
nums_in_arr2 = []
for x in arr2:
nums_in_arr2.extend([x] * count[x])
count.pop(x)
nums_not_in_arr2 = []
for x, y in count.items():
nums_not_in_arr2.extend([x] * y)
nums_not_in_arr2.sort()
return nums_in_arr2 + nums_not_in_arr2
|
因为题目中给定了元素大小是不超过 1000 的整数，所以可以直接使用一个数组对元素进行计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
count = [0] * (max(arr1) + 1)
for x in arr1:
count[x] += 1
ans = []
for x in arr2:
ans.extend([x] * count[x])
count[x] = 0
for x, i in enumerate(count):
if i:
ans.extend([x] * i)
return ans
|
自定义排序函数。
| class Solution:
def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
idx = {x: i for i, x in enumerate(arr2)}
len_arr2 = len(arr2)
def cmp(x: int) -> int:
return idx[x] - len_arr2 if x in idx else x
arr1.sort(key=cmp)
return arr1
|