1310. 子数组异或查询

2021-05-29 23:01

阅读：555

标签：wan amp ++i 直接 if判断 continue 时间复杂度 target 异或

思路：
还是异或的题。
因为我们前一道题已经得到一个算法,(3 ^ 4 ^ 5) = (1 ^ 2) ^ (1 ^ 2 ^ 3 ^ 4 ^ 5),所以在这题也可以通过该算法来减少异或次数。
我们有个很直接的想法就是从queries没获取一个查询范围，就从L-R的异或，那么最坏时间复杂度就是O(n*m)，因为n个查询范围可能查询m个数组项来异或。
通过上述的算法我们能简化到O(n)的时间复杂度。
所以我们要求解前缀异或结果，加入我们得到的查询范围是[2,3]，那么我们通过前缀异或结果[0,1] ^ [0,3] 即可得到2 ^ 3的结果，只用进行一次异或。

所以我们通过一个数组记录0-i的异或结果，最后每获得一个查询范围直接用前缀异或结果异或即可。

代码：

class Solution {
public:
    vector xorQueries(vector& arr, vector>& queries) {
        int n1 = arr.size();
        int n2 = queries.size();
        vector prexor(n1);
        vector res;
        int now=0;
        for(int i=0;i0){  //因为[0,1] ^ [0,3] = 2 ^ 3 ,所以要L要减1，但L为0就不用处理，直接从前缀异或结果获得结果。所以要用if判断呢
                int resxor = prexor[queries[i][1]]^prexor[queries[i][0]-1];
                res.push_back(resxor);
                continue;
            }
            res.push_back(prexor[queries[i][1]]);
            
        }
        return res;
    }
};

1310. 子数组异或查询

标签：wan amp ++i 直接 if判断 continue 时间复杂度 target 异或

原文地址：https://www.cnblogs.com/Mrsdwang/p/14759408.html

上一篇：java 判断String是否包含指定字符串的4种方式

下一篇：Java创建对象内存分析

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：1310. 子数组异或查询
文章链接：http://soscw.com/index.php/essay/89294.html

亲，登录后才可以留言！

1310. 子数组异或查询

评论

热门文章

推荐文章

最新文章

置顶文章