3668. 重排完成顺序

English Version

题目描述

给你一个长度为 n 的整数数组 order 和一个整数数组 friends。

• order 包含从 1 到 n 的每个整数，且 恰好出现一次 ，表示比赛中参赛者按照 完成顺序 的 ID。
• friends 包含你朋友们的 ID，按照 严格递增 的顺序排列。friends 中的每个 ID 都保证出现在 order 数组中。

请返回一个数组，包含你朋友们的 ID，按照他们的 完成顺序 排列。

 

示例 1：

示例 2：

 

提示：

• 1 <= n == order.length <= 100
• order 包含从 1 到 n 的每个整数，且恰好出现一次
• 1 <= friends.length <= min(8, n)
• 1 <= friends[i] <= n
• friends 是严格递增的

解法

方法一：自定义排序

我们先根据 $\textit{order}$ 数组构建一个映射，记录每个 ID 的完成顺序。然后对 $\textit{friends}$ 数组进行排序，排序的依据就是这些 ID 在 $\textit{order}$ 中的完成顺序。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\textit{order}$ 的长度。

Python3

class Solution:
    def recoverOrder(self, order: List[int], friends: List[int]) -> List[int]:
        d = {x: i for i, x in enumerate(order)}
        return sorted(friends, key=lambda x: d[x])

Java

class Solution {
    public int[] recoverOrder(int[] order, int[] friends) {
        int n = order.length;
        int[] d = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            d[order[i]] = i;
        }
        return Arrays.stream(friends)
            .boxed()
            .sorted((a, b) -> d[a] - d[b])
            .mapToInt(Integer::intValue)
            .toArray();
    }
}

C++

class Solution {
public:
    vector<int> recoverOrder(vector<int>& order, vector<int>& friends) {
        int n = order.size();
        vector<int> d(n + 1);
        for (int i = 0; i < n; ++i) {
            d[order[i]] = i;
        }
        sort(friends.begin(), friends.end(), [&](int a, int b) {
            return d[a] < d[b];
        });
        return friends;
    }
};

Go

func recoverOrder(order []int, friends []int) []int {
	n := len(order)
	d := make([]int, n+1)
	for i, x := range order {
		d[x] = i
	}
	sort.Slice(friends, func(i, j int) bool {
		return d[friends[i]] < d[friends[j]]
	})
	return friends
}

TypeScript

function recoverOrder(order: number[], friends: number[]): number[] {
    const n = order.length;
    const d: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        d[order[i]] = i;
    }
    return friends.sort((a, b) => d[a] - d[b]);
}