Easy

题目描述

给你一个长度为 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 严格递增

提示：

  • 使用哈希集合从 friends 中快速查找朋友
  • 遍历 order，检查集合以按完赛顺序收集你的朋友

解题思路

这道题的核心思路是根据给定的完赛顺序，筛选出朋友们的完赛顺序。

解法分析：

最直观的解法是使用哈希集合优化查找。由于我们需要按照 order 中的顺序来筛选 friends 中的元素，可以：

  1. 哈希集合法（推荐）： 将 friends 数组转换为哈希集合，然后遍历 order 数组，对每个元素检查是否在朋友集合中。如果是，就加入结果数组。时间复杂度 O(n)，空间复杂度 O(m)，其中 m 是朋友数量。

  2. 双指针法： 由于 friends 是有序的，也可以使用双指针技术。一个指针遍历 order，另一个指针遍历 friends，当找到匹配时移动 friends 指针。时间复杂度同样是 O(n)，但空间复杂度只有 O(1)（不包括结果数组）。

考虑到代码简洁性和可读性，推荐使用哈希集合法。这种方法直观易懂，性能也很好，特别是当朋友数量较小时（题目约束最多8个朋友）。

代码实现

class Solution {
public:
    vector<int> recoverOrder(vector<int>& order, vector<int>& friends) {
        unordered_set<int> friendSet(friends.begin(), friends.end());
        vector<int> result;
        
        for (int id : order) {
            if (friendSet.count(id)) {
                result.push_back(id);
            }
        }
        
        return result;
    }
};

class Solution:
    def recoverOrder(self, order: List[int], friends: List[int]) -> List[int]:
        friend_set = set(friends)
        result = []
        
        for person_id in order:
            if person_id in friend_set:
                result.append(person_id)
        
        return result

public class Solution {
    public int[] RecoverOrder(int[] order, int[] friends) {
        HashSet<int> friendSet = new HashSet<int>(friends);
        List<int> result = new List<int>();
        
        foreach (int id in order) {
            if (friendSet.Contains(id)) {
                result.Add(id);
            }
        }
        
        return result.ToArray();
    }
}

var recoverOrder = function(order, friends) {
    const friendSet = new Set(friends);
    const result = [];
    
    for (const id of order) {
        if (friendSet.has(id)) {
            result.push(id);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n 为 order 长度，m 为 friends 长度。构建哈希集合需要 O(m)，遍历 order 需要 O(n)
空间复杂度O(m)哈希集合存储朋友 ID 需要 O(m) 空间，结果数组不计入额外空间