xcode 降低确定数组中出现次数为奇数的元素的函数的时间复杂度

qrjkbowd  于 2023-03-09  发布在  其他
关注(0)|答案(1)|浏览(127)

我想减少这个函数的时间复杂度,它应该取一个向量,如下所示:
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%的表现。

cvxl0en2

cvxl0en21#

编码面试之所以会被打破,其中一个原因是,你只需要记住一组算法,然后根据需要编写,这需要知道XOR(异或)的行为。
简而言之:

A | B | A^B
-----------
0 | 0 | 0
- | - | -
0 | 1 | 1
- | - | - 
1 | 0 | 1
- | - | -
1 | 1 | 0

要点是,任何与自身异或的值都是0,所以如果一个值A与自身异或奇数次,结果是A。
这意味着所有出现偶数次的值将相互抵消,剩下的唯一值将是出现奇数次的值。

#include <iostream>
#include <vector>

int solution(std::vector<int> const& A)
{
  int occursOddNumberOfTimes = 0;

  for (const auto& i : A) {
    occursOddNumberOfTimes ^= i;
  }

  return occursOddNumberOfTimes;
}

int main() {
  std::vector<int> v{30, 15, 12, 15, 15, 12, 30};

  std::cout << solution(v) << '\n';
}

输出:

❯ ./a.out 
15

该算法只需遍历原向量一次,其性能为O(N),空间复杂度也为O(N),不需要额外的容器,只需要原向量。

相关问题