为什么这个解决方案比另一个更快？

Question

问题是 Leetcode 的 N-Repeated Element in Size 2N Array

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return元素重复N次

我很困惑，请帮忙！

更快的代码

    class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        auto it = A.begin();
        while(it!=A.end())
        {
            if(count(A.begin(),A.end(),*it)>1)
            {
                break;
            }
            else
                it++;              
        }
        return *it;
    }
};

较慢的代码

    class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        unordered_map<int,int> u;
        int rep;
        for(auto i: A){
            u[i]++;
            if(u[i]>1){
                rep=i;
            }
        }
        
        return rep;
    }
};

Answer 1

这是使用上述方法的一些（未经测试的）代码。我确实假设输入数据采用所描述的形式。如果不是这种情况，此代码将出错。

class Solution
{
public:
    int repeatedNTimes(vector<int>& A) {
        // check for alternating elements at even indexes
        if (A[0] == A[2])
           return A[0];
        // check for alternating elements at odd indexes
        if (A[1] == A[3])
           return A[1];
        // check for first and last being the same
        if (A.front() == A.back())
           return A.front();
        // check adjacent elements
        for (size_t i = 0;; ++i)
        {
            if (A[i] == A[i + 1])
                return A[i];
        }
        return -1;
    }
};

编辑

想到一个bug，我的算法只有在相邻环绕时才有效，即第一个和最后一个元素也被认为是相邻的。我也添加了代码来检查这种可能性。

为什么这个解决方案比另一个更快？

Why is this soln faster than the other?

c++

arrays

hashmap

unordered-map