我想减少这个函数的时间复杂度,它应该取一个向量,如下所示:
A=[30、15、12、15、15、12、30]
以及输出15,出现奇数次的元素。
int solution(vector<int> &A)
{
int value=0;
int count=0;
vector<vector<int>> B;
for (int i=0; i<A.size(); i++)
{
count = 0;
for (int j=0; j<A.size(); j++)
{
if (A[i]==A[j])
count++;
}
if (i==0)
{
B.push_back({count, A[i]});
}
else
{
for (int x=0; x<B.size(); x++)
{
if (B[x][1]==A[i])
break;
else if(x==(B.size()-1))
{
B.push_back({count, A[i]});
}
}
}
}
for (int i=0; i<B.size(); i++)
{
if ((B[i][0]%2)!=0)
value = B[i][1];
}
return value;
}
这是一次编码面试的练习,给了我25%的表现。
1条答案
按热度按时间cvxl0en21#
编码面试之所以会被打破,其中一个原因是,你只需要记住一组算法,然后根据需要编写,这需要知道XOR(异或)的行为。
简而言之:
要点是,任何与自身异或的值都是0,所以如果一个值A与自身异或奇数次,结果是A。
这意味着所有出现偶数次的值将相互抵消,剩下的唯一值将是出现奇数次的值。
输出:
该算法只需遍历原向量一次,其性能为O(N),空间复杂度也为O(N),不需要额外的容器,只需要原向量。