C++中如何优化同大小乱序字符数组的元素唯一索引查找复杂度？

当然可以！我们完全能把时间复杂度降到O(n logn)甚至平均O(n)的级别，下面给你详细说说几种C++的实现思路，还有对应的代码示例：

方法1：哈希表映射（平均O(n)时间） #

这是效率最高的方案，核心思路是先把数组a的元素和它的1-based索引做一个映射表，之后遍历数组b时直接查表就能得到结果。

实现步骤： #

• 遍历数组a，用unordered_map存储每个字符对应的1-based索引，这一步是O(n)时间。
• 遍历数组b，对每个字符直接从哈希表中取出对应的索引，平均每次查询是O(1)时间，总时间复杂度平均为O(n)。

C++代码示例： #

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    // 示例数组，你可以替换成自己的输入
    vector<char> a = {'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    vector<char> b = {'x', 'z', 'y', 'a', 'b', 'g', 'd', 'e', 'f', 'c'};
    
    unordered_map<char, int> char_pos;
    // 构建字符到索引的映射（1-based）
    for (int i = 0; i < a.size(); ++i) {
        char_pos[a[i]] = i + 1;
    }
    
    vector<int> result;
    result.reserve(b.size()); // 提前分配空间，优化性能
    for (char c : b) {
        // 这里假设b中所有元素都在a中存在，如果需要处理不存在的情况，可以加判断
        result.push_back(char_pos[c]);
    }
    
    // 输出结果
    for (size_t i = 0; i < result.size(); ++i) {
        if (i != 0) cout << ", ";
        cout << result[i];
    }
    cout << endl;
    
    return 0;
}

注意事项： #

• 这个方案要求数组a中的元素是唯一的（毕竟要找“唯一位置”），如果a中有重复元素，哈希表会覆盖之前的索引，这时候需要根据需求调整（比如存储所有出现的索引）。
• unordered_map的最坏时间复杂度是O(n²)（极端哈希冲突情况），但实际工程中几乎不会遇到，平均性能非常好。

方法2：排序+二分查找（O(n logn)时间） #

如果不想用哈希表，或者元素类型更适合排序（比如char、int这类原生类型），可以用排序加二分查找的方案，时间复杂度稳定在O(n logn)。

实现步骤： #

• 创建一个存储“字符-索引”对的数组，把a中的每个字符和对应的1-based索引存进去。
• 对这个数组按字符值排序，排序的时间是O(n logn)。
• 遍历数组b，对每个字符用lower_bound进行二分查找，找到对应的索引，每次二分是O(logn)时间，总时间O(n logn)。

C++代码示例： #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<char> a = {'x', 'y', 'z', 'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    vector<char> b = {'x', 'z', 'y', 'a', 'b', 'g', 'd', 'e', 'f', 'c'};
    
    // 存储字符和对应的1-based索引
    vector<pair<char, int>> a_with_index;
    for (int i = 0; i < a.size(); ++i) {
        a_with_index.emplace_back(a[i], i + 1);
    }
    
    // 按字符值排序
    sort(a_with_index.begin(), a_with_index.end());
    
    vector<int> result;
    result.reserve(b.size());
    for (char c : b) {
        // 二分查找第一个不小于c的元素
        auto it = lower_bound(a_with_index.begin(), a_with_index.end(), make_pair(c, 0));
        if (it != a_with_index.end() && it->first == c) {
            result.push_back(it->second);
        } else {
            // 处理元素不存在的情况，这里默认返回-1，你可以根据需求调整
            result.push_back(-1);
        }
    }
    
    // 输出结果
    for (size_t i = 0; i < result.size(); ++i) {
        if (i != 0) cout << ", ";
        cout << result[i];
    }
    cout << endl;
    
    return 0;
}

注意事项： #

• 同样要求a中的元素唯一，否则二分查找可能返回错误的索引（比如重复元素中靠后的那个）。
• 这个方案的时间复杂度是稳定的O(n logn)，不会出现哈希表那样的极端情况，适合对稳定性要求高的场景。

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