c/c++开发分享在重复元素XOR运算符的数组中找到两个非重复元素?

假设我有一个包含2n + 2个元素的数组。 数组中的n个元素出现两次,剩下的两个元素是唯一的。 你必须在O(n)时间和O(1)空间中解决这个问题。 其中一个解决方案是使用XOR。 但我无法理解这一点。 任何人都可以帮助我,或者可以给我更好的解决方案吗?

问题和解决方案的链接就是这个

    首先 – 注意每个a a xor a == 0

    假设您有两个唯一的数字 – x,y

    如果你对每个元素进行xor,你最终得到一个数字,它等于x xor y (因为每个dupe对自己都无效),并且至少有一个“up”位。 选择这一位(如果有多于一个,你可以选择哪一位),并将列表拆分为两个子列表:
    (1)所有设置此位的数字。
    (2)所有未设置此位的数字。

    其中一个唯一的数字有这个位,另一个没有(否则 – 它首先不是“向上”),所以你在每个列表中有一个唯一的数字。

    再次迭代每个列表,并对所有元素执行xor,结果是此列表中的唯一编号,因为每个重复对都会使其自身无效。

      以上就是c/c++开发分享在重复元素XOR运算符的数组中找到两个非重复元素?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注(猴子技术宅)。

      本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

      如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/545939.html

      发表评论

      电子邮件地址不会被公开。 必填项已用*标注