英文:
Reducing Time Complexity of Function That Determines the Element in the Array That Has an Odd Number of Occurrences
问题
我想要优化这个函数的时间复杂度，该函数的目标是从类似以下的向量中取出出现奇数次的元素，比如：
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%的性能。
英文:
I would like to reduce the time complexity for this function that is supposed to take a vector like the following:
A=[30,15,12,15,15,12,30]
and output 15, the element that occurs an odd number of times.
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;
}
This is to practice for a coding interview and gave me a performance of 25%.
答案1
得分: 2
编程面试存在众多固有问题之一是你期望只是记住一组算法，可以随时写出来。其中一个需要了解XOR（异或）行为的情况如下：
简而言之：
A | B | A^B
-----------
0 | 0 | 0
- | - | -
0 | 1 | 1
- | - | -
1 | 0 | 1
- | - | -
1 | 1 | 0
要点是任何值与自身进行XOR运算的结果都是0。因此，如果一个值A与自身进行奇数次XOR运算，结果将是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)，因为不需要额外的容器，只需使用原始向量。
英文:
One of the many reasons that coding interviews are inherently broken is that you are expected to simply have a set of algorithms memorized that you can write on demand. This one requires knowing the behavior of XOR (exclusive or).
Simply put:
A | B | A^B
-----------
0 | 0 | 0
- | - | -
0 | 1 | 1
- | - | -
1 | 0 | 1
- | - | -
1 | 1 | 0
The gist is that any value XOR'd with itself is 0. So if a value A is XOR'd with itself an odd number of times, the result is A.
This means that all values that occur an even amount of times will cancel each other out, and the only value left will be the one that occurred an odd number of times.
#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';
}
Output:
❯ ./a.out
15
The performance of this algorithm is O(N), as it only needs to traverse the original vector once. The space complexity is also O(N), as no extra containers are needed, just the original vector.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论