我陷入一个难题,即找到一个xor为0的子数组。我读到某个地方,可以使用TRIE数据结构完成此操作,但是我想要数组的开始和结束索引。
例如,考虑一个数组
a = [3,6,13,8 15]
子数组从0到3,即[3,6,13,8]的xor等于0。(3 xor 6 xor 13 xor 8 = 0)我正在寻找一种算法,无法找到那些索引(在这种情况下为[0,3])。
详细的答案将非常有帮助。 p>
更新 我尝试了蛮力方法来检查所有[i,j]对的xor值。由于没有,所以给了TLE。数组中元素的最大数量为10 ^ 5
我尝试了提到的解决方案在这里,但这没有给出索引。
我正在寻找一种算法
解决方案此解决方案采用 O(n )的复杂度。充分利用 unordered_map 。
vector< int> a = {3,6,13,8,15}; unordered_map< int,int> hashMap; int number_of_elements = a.size(); hashMap [0] = -1; int xor_sum = 0; for(int i = 0; i< number_of_elements; i ++){ xor_sum ^ = a [i]; if(hashMap.find(xorSum)!= hashMap.end()){ cout<< hashMap [xorSum] + 1<< <<我<<恩德尔休息时间; } hashMap [xor_sum] = i; }
I'm stuck at one problem i.e. to find a subarray whose xor is 0. I read somewhere that this can be done using TRIE data structure but I want the starting and ending indices of the array.
For example, consider an array
a = [3, 6, 13, 8 15]
The subarray from 0 to 3 i.e. [3, 6, 13, 8] has xor equal to 0. (3 xor 6 xor 13 xor 8 = 0) I'm in search for an algorithm than can find those indices ([0, 3] in this case).
Detailed answer would be very helpful.
Update I tried the brute Force approach find checking xor for all pairs of [i, j]. This gives TLE since the no. of elements in the array could be upto 10^5
The I tried a solution mentioned here but this doesn't give indices.
I'm looking for an algorithm with O(nLogn) or possibly O(n) complexity.
解决方案This solution take O(n) complexity also. Take the benefit of unordered_map.
vector<int> a = {3,6,13,8,15}; unordered_map<int, int> hashMap; int number_of_elements = a.size(); hashMap[0] = -1; int xor_sum = 0; for(int i = 0; i < number_of_elements; i++) { xor_sum ^= a[i]; if(hashMap.find(xorSum) != hashMap.end()) { cout << hashMap[xorSum] + 1 << " " << i << endl; break; } hashMap[xor_sum] = i; }
更多推荐
查找xor为0的子数组
发布评论