题目

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

题解

public int singleNumber(int[] nums) {
    Arrays.sort(nums);
    for (int i = 2; i < nums.length; i += 3) {
        if (nums[i] != nums[i - 2]) {
            return nums[i - 2];
        }
    }

    return nums[nums.length - 1];
}

public int singleNumber1(int[] nums) {
    // x ^ 0 = x
    // x ^ x = 0
    // ab ^ 00 = ab
    // ab ^ ab = 0
    // x & ~x = 0
    // x & ~0 = x
    int a = 0, b = 0;
    for (int x : nums) {
        b = (b ^ x) & ~a;
        a = (a ^ x) & ~b;
    }
    return b;
}