3668. 重排完成顺序

题目描述

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

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

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

示例 1：

输入：order = [3,1,2,5,4], friends = [1,3,4]

输出：[3,1,4]

解释：

完成顺序是 [3, 1, 2, 5, 4]。因此，你朋友的完成顺序是 [3, 1, 4]。

示例 2：

输入：order = [1,4,5,3,2], friends = [2,5]

输出：[5,2]

解释：

完成顺序是 [1, 4, 5, 3, 2]。因此，你朋友的完成顺序是 [5, 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}\) 的长度。

Python3JavaC++GoTypeScript

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])

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();
    }
}

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;
    }
};

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
}

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]);
}

3668. 重排完成顺序

题目描述

解法

方法一：自定义排序

评论