题解 | #被打乱的异或和#

被打乱的异或和

https://www.nowcoder.com/practice/116db6858c424fb89b821125053bbc15

题目链接

被打乱的异或和

题目描述

有一个长度为 的原始整数数组 。计算出该数组所有元素的按位异或和,记为 。然后将 添加到数组 的末尾,形成一个长度为 的新数组。最后,这个新数组被随机打乱,得到了我们看到的输入数组

给定被打乱后的数组 ,我们需要找回原始的异或和 。题目保证至少有一个解,若有多个可能的解,输出任意一个即可。

解题思路

这道题的核心在于巧妙地运用异或运算的性质。

我们来回顾一下异或(XOR, )的几个关键性质:

  1. 交换律和结合律, 。这意味着一串数字的异或和与它们的顺序无关。
  2. 自反性。任何数与自身异或的结果是 0。
  3. 单位元。任何数与 0 异或的结果是它本身。

设原始数组是 。 其异或和是 。 将 添加后,数组变为 。 输入的数组 的一个随机排列。

根据异或的交换律和结合律,数组 中所有元素的异或和与数组 相同。我们来计算一下这个总异或和:

我们知道括号里的部分就是 的定义,所以:

根据自反性,。所以:

这意味着,无论原始数组是什么,被打乱后的输入数组 的所有元素异或和永远是 0

现在,我们如何找到 ?题目要求我们输出任意一个可能的

让我们从输入数组 任意选择一个元素,比如 ,然后假设它就是我们要找的

如果这个假设成立,那么数组 中剩下的 个元素就应该是原始数组

为了验证这个假设,我们需要检查这剩下的 个元素的异或和是否真的等于我们假设的 (也就是 )。

剩下的 个元素的异或和可以这样计算:将 的总异或和,再与 进行一次异或(这相当于从总和中“移除”)。

我们已经证明了 ,所以:

这个结果说明,我们计算出的“剩下元素的异或和”恰好就等于我们一开始假设的那个元素

这个推导对于我们从数组 中选择的任何一个元素 都成立。

结论:输入数组 中的每一个元素都是一个合法的解。既然题目允许我们输出任意一个,最简单的做法就是直接输出数组的第一个元素。

代码

#include <iostream>

void solve() {
    int m;
    std::cin >> m;
    // 只需要读取第一个数字作为答案
    int first_num;
    std::cin >> first_num;
    std::cout << first_num << std::endl;
    // 读取并丢弃剩下的 m-1 个数字
    for (int i = 1; i < m; ++i) {
        int temp;
        std::cin >> temp;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int m = sc.nextInt();
            // 只需要读取第一个数字作为答案
            int firstNum = sc.nextInt();
            System.out.println(firstNum);
            // 读取并丢弃剩下的 m-1 个数字
            for (int i = 1; i < m; i++) {
                sc.nextInt();
            }
        }
    }
}
import sys

def solve():
    m = int(sys.stdin.readline())
    # 读取整行,并只取第一个数字作为答案
    nums = sys.stdin.readline().split()
    print(nums[0])

def main():
    t_str = sys.stdin.readline()
    if not t_str:
        return
    t = int(t_str)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法:数学/位运算。基于对异或运算性质的分析,我们得出结论:输入数组中的任何一个元素都是一个有效的答案。因此,我们只需读取并输出第一个元素。
  • 时间复杂度:对于每个测试用例,我们读取 个整数,但只处理第一个。总时间复杂度取决于读入所有数字所需的时间,即 ,其中 是所有测试用例的数组长度之和。
  • 空间复杂度:我们不需要存储整个数组,只需要存储单个变量。因此,空间复杂度为
全部评论

相关推荐

彧未sr:查看图片
投递牧原集团等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务