如何按主数组指定顺序高效获取查询数组子集？

当然有更高效的解决方案！先聊聊朴素方案的痛点：如果是遍历查询数组的每个元素，再逐个去主数组里查找位置来排序，时间复杂度是O(n*m)（n为主数组长度，m为查询数组长度），数据量一大就会很慢。下面给你两种更优的思路：

1. 哈希映射+自定义排序（时间复杂度 O(n + m log m)） #

核心思路是空间换时间：先给主数组建立一个元素到索引的哈希映射，这样查询任意元素在主数组的位置只需要O(1)时间，之后用这个映射作为排序依据对查询数组排序。

举个Python的实现例子：

# 示例主数组
master = ["apple", "banana", "cherry", "date"]
# 示例查询数组
query = ["cherry", "apple", "banana"]

# 构建元素到索引的映射字典
index_map = {value: idx for idx, value in enumerate(master)}
# 按照主数组的索引值排序查询数组
sorted_query = sorted(query, key=lambda x: index_map[x])

print(sorted_query)  # 输出: ['apple', 'banana', 'cherry']

这种方案在查询数组规模中等时非常实用，代码简洁易读，性能也远优于朴素方案。

2. 计数统计+遍历主数组（时间复杂度 O(n + m)） #

如果查询数组的规模特别大（比如百万级元素），可以进一步优化到线性时间：先统计查询数组中每个元素的出现次数，再遍历主数组，把出现过的元素按统计次数批量加入结果列表。

同样用Python实现：

from collections import Counter

master = ["apple", "banana", "cherry", "date"]
query = ["cherry", "apple", "banana", "apple"]

# 统计查询数组中各元素的出现次数
item_counts = Counter(query)
sorted_query = []

# 遍历主数组，按顺序收集查询数组中的元素
for item in master:
    if item in item_counts:
        sorted_query.extend([item] * item_counts[item])

print(sorted_query)  # 输出: ['apple', 'apple', 'banana', 'cherry']

这个方案完全避开了排序操作，时间复杂度是线性的，在大数据量场景下性能优势非常明显。

额外说明 #

如果主数组存在重复元素，需要先明确排序规则：

• 若以元素在主数组中第一次出现的索引为准，用第一种方案即可；
• 若要保留主数组中重复元素的相对顺序（比如主数组是["a", "b", "a"]，查询数组是["a", "a"]，希望结果对应主数组的两个位置顺序），可以修改映射为记录元素的索引列表，再结合计数来处理，但这种场景比较少见，具体可以根据需求调整。

内容的提问来源于stack exchange，提问作者user_1_1_1