LeetCode 1122: Relative Sort Array (Order Map + Stable Bucketing)
LeetCode 1122ArraySortingCountingToday we solve LeetCode 1122 - Relative Sort Array.
Source: https://leetcode.com/problems/relative-sort-array/
English
Problem Summary
Given arr1 and arr2 where all values in arr2 are distinct and appear in arr1, sort arr1 so that numbers in arr2 come first in the same order as arr2, and all remaining numbers come after them in ascending order.
Key Insight
Because values are in range [0, 1000], a counting array is the cleanest approach: count every value in arr1, output values by arr2 order first, then output leftovers from small to large.
Algorithm
1) Build frequency array cnt[1001] from arr1.
2) For each x in arr2, append x exactly cnt[x] times and clear cnt[x].
3) Scan v = 0..1000, append each leftover value v, cnt[v] times.
4) Return the built result.
Complexity Analysis
Time: O(n + 1001), where n = arr1.length.
Space: O(1001) for counting array.
Common Pitfalls
- Forgetting to clear counts after consuming arr2 values.
- Sorting leftover numbers before handling arr2 order (wrong priority).
- Overengineering with custom comparators when counting is simpler and faster.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] cnt = new int[1001];
for (int x : arr1) cnt[x]++;
int[] ans = new int[arr1.length];
int idx = 0;
for (int x : arr2) {
while (cnt[x]-- > 0) {
ans[idx++] = x;
}
cnt[x] = 0;
}
for (int v = 0; v <= 1000; v++) {
while (cnt[v]-- > 0) {
ans[idx++] = v;
}
}
return ans;
}
}func relativeSortArray(arr1 []int, arr2 []int) []int {
cnt := make([]int, 1001)
for _, x := range arr1 {
cnt[x]++
}
ans := make([]int, 0, len(arr1))
for _, x := range arr2 {
for cnt[x] > 0 {
ans = append(ans, x)
cnt[x]--
}
}
for v := 0; v <= 1000; v++ {
for cnt[v] > 0 {
ans = append(ans, v)
cnt[v]--
}
}
return ans
}class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<int> cnt(1001, 0);
for (int x : arr1) cnt[x]++;
vector<int> ans;
ans.reserve(arr1.size());
for (int x : arr2) {
while (cnt[x] > 0) {
ans.push_back(x);
cnt[x]--;
}
}
for (int v = 0; v <= 1000; v++) {
while (cnt[v] > 0) {
ans.push_back(v);
cnt[v]--;
}
}
return ans;
}
};class Solution:
def relativeSortArray(self, arr1: list[int], arr2: list[int]) -> list[int]:
cnt = [0] * 1001
for x in arr1:
cnt[x] += 1
ans = []
for x in arr2:
while cnt[x] > 0:
ans.append(x)
cnt[x] -= 1
for v in range(1001):
while cnt[v] > 0:
ans.append(v)
cnt[v] -= 1
return ansvar relativeSortArray = function(arr1, arr2) {
const cnt = new Array(1001).fill(0);
for (const x of arr1) cnt[x]++;
const ans = [];
for (const x of arr2) {
while (cnt[x] > 0) {
ans.push(x);
cnt[x]--;
}
}
for (let v = 0; v <= 1000; v++) {
while (cnt[v] > 0) {
ans.push(v);
cnt[v]--;
}
}
return ans;
};中文
题目概述
给定数组 arr1 和 arr2，其中 arr2 中元素互不相同且都出现在 arr1 中。要求将 arr1 重新排序：先按 arr2 的相对顺序放置这些元素，剩余元素再按升序放到末尾。
核心思路
数值范围固定在 [0,1000]，非常适合计数数组。先统计频次，再先输出 arr2 指定顺序，最后按数值从小到大输出剩余元素。
算法步骤
1）用 cnt[1001] 统计 arr1 每个值出现次数。
2）按 arr2 顺序，把每个值输出 cnt[x] 次。
3）再从 0 到 1000 扫描，把未输出的值按升序补齐。
4）返回结果数组。
复杂度分析
时间复杂度：O(n + 1001)。
空间复杂度：O(1001)。
常见陷阱
- 输出完 arr2 元素后忘记扣减频次，导致重复输出。
- 先处理升序尾部再处理 arr2，会破坏题目要求的优先顺序。
- 使用通用排序比较器但忽略边界，复杂且更容易出错。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] cnt = new int[1001];
for (int x : arr1) cnt[x]++;
int[] ans = new int[arr1.length];
int idx = 0;
for (int x : arr2) {
while (cnt[x]-- > 0) {
ans[idx++] = x;
}
cnt[x] = 0;
}
for (int v = 0; v <= 1000; v++) {
while (cnt[v]-- > 0) {
ans[idx++] = v;
}
}
return ans;
}
}func relativeSortArray(arr1 []int, arr2 []int) []int {
cnt := make([]int, 1001)
for _, x := range arr1 {
cnt[x]++
}
ans := make([]int, 0, len(arr1))
for _, x := range arr2 {
for cnt[x] > 0 {
ans = append(ans, x)
cnt[x]--
}
}
for v := 0; v <= 1000; v++ {
for cnt[v] > 0 {
ans = append(ans, v)
cnt[v]--
}
}
return ans
}class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
vector<int> cnt(1001, 0);
for (int x : arr1) cnt[x]++;
vector<int> ans;
ans.reserve(arr1.size());
for (int x : arr2) {
while (cnt[x] > 0) {
ans.push_back(x);
cnt[x]--;
}
}
for (int v = 0; v <= 1000; v++) {
while (cnt[v] > 0) {
ans.push_back(v);
cnt[v]--;
}
}
return ans;
}
};class Solution:
def relativeSortArray(self, arr1: list[int], arr2: list[int]) -> list[int]:
cnt = [0] * 1001
for x in arr1:
cnt[x] += 1
ans = []
for x in arr2:
while cnt[x] > 0:
ans.append(x)
cnt[x] -= 1
for v in range(1001):
while cnt[v] > 0:
ans.append(v)
cnt[v] -= 1
return ansvar relativeSortArray = function(arr1, arr2) {
const cnt = new Array(1001).fill(0);
for (const x of arr1) cnt[x]++;
const ans = [];
for (const x of arr2) {
while (cnt[x] > 0) {
ans.push(x);
cnt[x]--;
}
}
for (let v = 0; v <= 1000; v++) {
while (cnt[v] > 0) {
ans.push(v);
cnt[v]--;
}
}
return ans;
};
Comments