2026-01-31：重排完成顺序。用go语言，给定两个数组：order 长度为 n，包含 1 到 n 的所有编号且互不重复，数组中元素的先后位置表示选手

福大大架构师每日一题

发布于 2026-02-09 14:43:31

610

2026-01-31：重排完成顺序。用go语言，给定两个数组：order 长度为 n，包含 1 到 n 的所有编号且互不重复，数组中元素的先后位置表示选手完成比赛的先后次序；friends 是一个按升序列出的朋友编号集合，且每个编号都出现在 order 中。请输出一个新的数组，把 friends 中的编号按它们在 order 中出现的先后顺序重新排列并返回。

1 <= n == order.length <= 100。

order 包含从 1 到 n 的每个整数，且恰好出现一次。

1 <= friends.length <= min(8, n)。

1 <= friends[i] <= n。

friends 是严格递增的。

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

输出：[3,1,4]。

解释：

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

题目来自力扣3668。

📌 步骤一：初始化与标记准备

首先，代码会创建一个名为 isFriend 的布尔型切片（slice），其长度为 n+1（n 是 order 数组的长度）。这个切片的作用就像一个"标记位图"，索引代表选手的编号。接着，代码会遍历输入的 friends 数组，对于其中的每一个朋友编号，在 isFriend 切片的对应索引位置标记为 true。这相当于快速登记了哪些编号是我们的朋友。

📌 步骤二：按完成顺序筛选朋友

然后，代码开始按照比赛的真实完成顺序（即 order 数组的顺序）来筛选朋友。它会依次检查 order 数组中的每一个编号。对于每个编号，它去查询 isFriend 标记数组。如果发现当前编号被标记为 true（说明这个选手是朋友），就将这个编号添加到一个新的结果数组 ans 中。这个结果数组在创建时已经根据朋友的数量预分配了内存，这有助于提升后续添加操作的效率。

📌 步骤三：返回结果

当 order 数组被完全遍历后，结果数组 ans 中就包含了所有朋友编号，并且它们的顺序严格遵循了在 order 中出现的先后次序。最后，将这个结果数组返回。

💡 复杂度分析

• 总的时间复杂度：O(n)。这是因为代码主要执行了两个简单的线性循环：第一个循环遍历 friends 数组（长度最大为8）来建立标记，其时间复杂度为 O(m)，其中 m 是朋友数量。第二个循环遍历 order 数组（长度为 n）来筛选朋友，其时间复杂度为 O(n)。由于题目中朋友数量 m 远小于 n（m ≤ 8），所以总的时间复杂度由代价更高的 O(n) 循环主导，记为 O(n)。
• 总的额外空间复杂度：O(n)。这主要是由创建的 isFriend 标记数组导致的，该数组的长度为 n+1，因此需要 O(n) 的额外空间。结果数组 ans 存储朋友编号，其长度最大为8，属于常数空间开销 O(1)。所以，整体的额外空间复杂度是 O(n)。

Go完整代码如下：

package main

import (
    "fmt"
)

func recoverOrder(order, friends []int) []int {
    n := len(order)
    isFriend := make([]bool, n+1)
    for _, x := range friends {
        isFriend[x] = true
    }

    ans := make([]int, 0, len(friends)) // 预分配空间
    for _, x := range order {
        if isFriend[x] {
            ans = append(ans, x)
        }
    }
    return ans
}

func main() {
    order := []int{3, 1, 2, 5, 4}
    friends := []int{1, 3, 4}
    result := recoverOrder(order, friends)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def recover_order(order: List[int], friends: List[int]) -> List[int]:
    friend_set = set(friends)
    return [x for x in order if x in friend_set]

def main():
    order = [3, 1, 2, 5, 4]
    friends = [1, 3, 4]
    result = recover_order(order, friends)
    print(result) 

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

vector<int> recoverOrder(const vector<int>& order, const vector<int>& friends) {
    // 使用哈希集合的方法（更高效）
    unordered_set<int> friendSet(friends.begin(), friends.end());

    vector<int> ans;
    ans.reserve(friends.size()); // 预分配空间

    for (int x : order) {
        if (friendSet.find(x) != friendSet.end()) {
            ans.push_back(x);
        }
    }

    return ans;
}

// 如果要用类似Go版本的布尔数组方法（要求数值范围不大）
vector<int> recoverOrderBoolArray(const vector<int>& order, const vector<int>& friends) {
    // 找到最大值来确定数组大小
    int maxVal = 0;
    for (int x : order) {
        if (x > maxVal) maxVal = x;
    }
    for (int x : friends) {
        if (x > maxVal) maxVal = x;
    }

    vector<bool> isFriend(maxVal + 1, false);
    for (int x : friends) {
        if (x <= maxVal) {
            isFriend[x] = true;
        }
    }

    vector<int> ans;
    ans.reserve(friends.size());

    for (int x : order) {
        if (x <= maxVal && isFriend[x]) {
            ans.push_back(x);
        }
    }

    return ans;
}

int main() {
    vector<int> order = {3, 1, 2, 5, 4};
    vector<int> friends = {1, 3, 4};

    vector<int> result = recoverOrder(order, friends);

    for (int x : result) {
        cout << x << " ";
    }
    cout << endl;

    return0;
}