🌕 260. 只出现一次的数字 III

难度: 🌕

问题描述

---

解法

class Solution {
    public int[] singleNumber(int[] nums) {
        // 思路：
        // 由于其他元素只出现 2 次，那么 2 个相同值相异或 == 0
        // 将所有元素相与之后，由于有 2 个其他元素，那么相异或值肯定存在 1
        // 找到结果中任意一个 1，根据它分成 2 部分，每部分对应一个值
        int sum = 0;
        for(int i : nums) {
            sum ^= i;
        }
        // 找到 sum 
        int pow = 0;
        // System.out.println(sum);
        while(true) {
            if((sum & (1 << pow)) != 0) {
                break;
            } else {
                pow ++;
            }
        }
        // 根据 1<< pow 分成 2 部分
        int left = 0;
        int right = 0;
        int monitor = (1 << pow);
        for(int i : nums) {
            if((i & monitor) == 0) {
                left ^= i;
            } else {
                right ^= i;
            }
        }
        return new int[] {left, right};
    }
}

---

输出