遇到一个空间负责度问题，求解答，
一个长度为 n 的数组，其中只有2个数字出现了奇数次，其他均出现偶数次，应该怎样使用优秀的时空复杂度快速找到这个数字？
展开
收起
1
条回答
写回答
写回答
-
主要是利用异或定理，若 a^b=x，则 a=b^x，b=x^a。 解法：1)假设这两个数分别为a、b，假设将数组中所有元素全部异或后结果为x，因为 a!=b，所以 x=a^b，且 x!=0 2)判断 x 中某位 bit 为 1 的位置，例如 x=0x00101100，那么 k=2/k=3/k=5 皆可，只需一个 ; 3)因为x中第k位为1表示a或b中有一个数的第k位也为1，另一个数第k位为 0；假设 a 的第 k 位为 1； 4)将 x 与数组中第 k 位为 1 的所有数字进行异或，最终结果得到 b； 5)将 x 与 b 异或，得到的结果即为 a
2021-12-23 18:05:15赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
