LeetCode 题解工作台
数组的相对排序
给你两个数组， arr1 和 arr2 ， arr2 中的元素各不相同， arr2 中的每个元素都出现在 arr1 中。 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。 示例 1： 输入：…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们先用哈希表 记录数组 中每个元素的位置。然后，我们将数组 中的每个元素映射成一个二元组 $(pos.get(x, 1000 + x), x)$，并对二元组进行排序。最后我们取出所有二元组的第二个元素并返回即可。 时间复杂度 $O(n \times \log n + m)$，空间复杂度 $O(n + m)$。其中 和 分别是数组 和 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例 1：
输入：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]
示例 2:
输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6] 输出：[22,28,8,6,17,44]
提示：
1 <= arr1.length, arr2.length <= 10000 <= arr1[i], arr2[i] <= 1000arr2中的元素arr2[i]各不相同arr2中的每个元素arr2[i]都出现在arr1中
解题思路
方法一：自定义排序
我们先用哈希表 记录数组 中每个元素的位置。然后，我们将数组 中的每个元素映射成一个二元组 ，并对二元组进行排序。最后我们取出所有二元组的第二个元素并返回即可。
时间复杂度 ，空间复杂度 。其中 和 分别是数组 和 的长度。
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))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n + m + k) |
| 空间 | O(k) |
面试官常问的追问
外企场景- question_mark
Look for an efficient implementation that minimizes unnecessary sorting.
- question_mark
Test the candidate's ability to use a hashmap for ordering and scanning.
- question_mark
Check how the candidate handles edge cases, such as when arr1 and arr2 are the same length.
常见陷阱
外企场景- error
Failing to account for elements in arr1 that aren't in arr2, leading to incorrect output.
- error
Not maintaining the relative order of elements in arr1 that match arr2.
- error
Not sorting the leftover elements of arr1 correctly at the end.
进阶变体
外企场景- arrow_right_alt
Handling cases where arr1 and arr2 contain repeated elements.
- arrow_right_alt
Optimizing space usage if constraints change, such as limiting space complexity to O(1).
- arrow_right_alt
Implementing a version that sorts arr1 directly without using a hashmap.