Easy

题目描述

给你两个数组，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 <= 1000
  • 0 <= arr1[i], arr2[i] <= 1000
  • arr2 中的元素 arr2[i] 各不相同
  • arr2 中的每个元素都出现在 arr1 中

解题思路

这道题要求按照 arr2 的相对顺序对 arr1 进行排序，可以用以下几种方法解决：

方法一：哈希表 + 自定义排序（推荐） 使用哈希表记录 arr2 中每个元素的位置索引，然后对 arr1 进行自定义排序。排序规则是：

  • 如果两个元素都在 arr2 中，按它们在 arr2 中的位置排序
  • 如果只有一个元素在 arr2 中，在 arr2 中的元素排在前面
  • 如果两个元素都不在 arr2 中，按升序排列

方法二：计数排序 先统计 arr1 中每个元素的出现次数，然后按照 arr2 的顺序依次输出对应数量的元素，最后将不在 arr2 中的元素按升序添加到结果末尾。

方法三：分离 + 排序 将 arr1 分为两部分：在 arr2 中的元素和不在 arr2 中的元素。对第一部分按 arr2 的顺序排序，对第二部分升序排序，最后合并。

代码实现

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> order;
        for (int i = 0; i < arr2.size(); i++) {
            order[arr2[i]] = i;
        }
        
        sort(arr1.begin(), arr1.end(), [&](int a, int b) {
            bool aInArr2 = order.count(a);
            bool bInArr2 = order.count(b);
            
            if (aInArr2 && bInArr2) {
                return order[a] < order[b];
            } else if (aInArr2) {
                return true;
            } else if (bInArr2) {
                return false;
            } else {
                return a < b;
            }
        });
        
        return arr1;
    }
};

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        order = {val: i for i, val in enumerate(arr2)}
        
        def compare(x):
            if x in order:
                return (0, order[x])
            else:
                return (1, x)
        
        arr1.sort(key=compare)
        return arr1

public class Solution {
    public int[] RelativeSortArray(int[] arr1, int[] arr2) {
        Dictionary<int, int> order = new Dictionary<int, int>();
        for (int i = 0; i < arr2.Length; i++) {
            order[arr2[i]] = i;
        }
        
        Array.Sort(arr1, (a, b) => {
            bool aInArr2 = order.ContainsKey(a);
            bool bInArr2 = order.ContainsKey(b);
            
            if (aInArr2 && bInArr2) {
                return order[a].CompareTo(order[b]);
            } else if (aInArr2) {
                return -1;
            } else if (bInArr2) {
                return 1;
            } else {
                return a.CompareTo(b);
            }
        });
        
        return arr1;
    }
}

var relativeSortArray = function(arr1, arr2) {
    const order = new Map();
    for (let i = 0; i < arr2.length; i++) {
        order.set(arr2[i], i);
    }
    
    return arr1.sort((a, b) => {
        const aInArr2 = order.has(a);
        const bInArr2 = order.has(b);
        
        if (aInArr2 && bInArr2) {
            return order.get(a) - order.get(b);
        } else if (aInArr2) {
            return -1;
        } else if (bInArr2) {
            return 1;
        } else {
            return a - b;
        }
    });
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)n 为 arr1 的长度，主要消耗在排序操作上
空间复杂度O(m)m 为 arr2 的长度，用于存储哈希表