vector与unordered_map的元素访问时间复杂度对比及InterviewBit算法题超时问题排查

I was solving the Largest Permutation problem and ran into a confusing issue: when I used an unordered_map to store the indices of array elements, my code hit a Time Limit Exceeded error. But when I switched to using a vector to implement the same index storage logic, the runtime efficiency improved significantly.

I know that theoretically, both unordered_map and vector have O(1) average access time. I've attached my working vector-based code below, and I'm wondering if there's something wrong with how I might have implemented the unordered_map version (I didn't save it, but the logic was identical—just replacing the vector with an unordered_map). Also, I suspect the difference might come from insertion or overhead differences between the two structures, but I'm not sure.

Here's my vector-based code:

vector<int> Solution::solve(vector<int> &A, int B) {
    int n=A.size();
    int cnt=0;
    for(int i=1;i<n;i++){
        if(A[i-1]>A[i]) cnt++;
    }
    if(cnt==n-1) return A;
    vector<int>mp(n+1,-1);
    for(int i=0;i<n;i++){
        mp[A[i]]=i;
    }
    int i=0;
    int temp=n;
    while(i<n && temp>=1 && B!=0){
        if(A[i]!=temp){
            cout<<A[i]<<" "<<temp<<endl;
            int x=A[i];
            A[i]=temp;
            A[mp[temp]]=x;
            mp[x]=mp[temp];
            mp[temp]=i;
            B=B-1;
        }
        i=i+1;
        temp=temp-1;
    }
    return A;
}

Let's break down why the vector approach is faster here: #

• Memory Locality & Cache Efficiency
  Vectors store elements in contiguous memory blocks. When you access mp[A[i]], the CPU can preload nearby memory into its cache, making subsequent accesses much faster. In contrast, unordered_map uses a hash table with non-contiguous bucket storage, leading to frequent cache misses that slow down operations.

• Hash Function Overhead
  Even with O(1) average access time, unordered_map requires computing a hash for your key (the array elements) every time you access or insert. For small integer keys like in this permutation problem, this hash computation is unnecessary and adds extra runtime cost. A vector uses direct memory offset calculation—no hash needed, just simple arithmetic.

• Initialization & Insertion Overhead
  Initializing a vector of size n+1 is a single contiguous memory allocation, which is extremely fast. unordered_map involves dynamic allocation for each bucket and element insertion, plus collision handling logic (even if collisions don't occur in practice), which adds up significantly for large input sizes.

• Guaranteed No Collisions
  Since the input is a permutation of integers from 1 to n, each value maps to exactly one index. The vector approach leverages this perfectly with no risk of collisions, while unordered_map still carries the overhead of collision checks that aren't needed here.

Quick Note on Your Code #

Your vector-based implementation is already optimal for this problem: it takes advantage of the permutation's properties to avoid hash table overhead entirely, while maintaining O(1) access time. Even a correctly implemented unordered_map version would have higher constant factors that make it too slow for large test cases.

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