题目描述

image.png

解题思路

本题要求时间复杂度为O(1)，空间复杂度为O(1)，那么只能暴力法和哈希法就不管用了。
此时可以考虑异或，异或^=含义：两个相同数字异或为 0 ，即对于任意整数 a 有 a⊕a=0 。因此，若将 nums 中所有数字执行异或运算，留下的结果则为 出现一次的数字 x。
那么将数组的每个数进行异或，得到的就是只出现1次的2个数的异或结果，例如：
a⊕a⊕b⊕b⊕…⊕x⊕y = 0⊕0⊕…⊕x⊕y = x⊕y ；
但我们需要返回2个数，而不是他们的异或结果！！！
但这2个数的异或结果肯定有一位不相同，我们可以使用m和刚才所有异或的结果进行相与如果为0，如果为0，此时m需要从右向左移动，继续判断，当不为0时，就是找到右边第一位为1，此时的m就可以区分异或的2个数。（找左边第一个1也可以，目的就是区分出2个数字，在进行分组）
然后再遍历一遍数组，分别对m相与，求出2个分组，再将每个分组相与，最后就可以的得到2个不相同且只出现一次的数。
image.png
更详细的解题思路🔗

  1. class Solution {
  2.     // 使用异或：相同为0，和0异或为非0那个数
  3.     public int[] singleNumbers(int[] nums) {
  4.         int n = 0, y = 0, m = 1, x = 0;
  5.         for (int num : nums) {
  6.             n ^= num;
  7.         }
  9.         while ((n & m) == 0) {
  10.             m <<= 1;
  11.         }
  13.         // 再分组异或
  14.         for (int num : nums) {
  15.             if ((num & m) != 0) x ^= num;
  16.             else y ^= num;
  17.         }
  19.         return new int[]{x, y};
  20.     }
  21. }