Java算法题-解析只出现一次的数字II问题

题目

给定一个非空整数数组，除了一个元素只出现一次之外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

引言

在这个算法问题中，我们将探讨一个与数组中数字出现次数相关的问题。问题的核心是在一个数组中，除了一个数字之外，其他所有数字都出现了三次。我们需要找到那个只出现一次的数字。

算法思路

我们可以使用位运算来解决这个问题。具体思路如下：

1. 定义两个变量 ones 和 twos，分别表示只出现一次的数字和出现两次的数字。
2. 遍历数组中的每个元素，将当前元素与 ones 做与运算，然后与 twos 做异或运算。这两步的目的是在 ones 中保留只出现一次的数字，而将出现两次的数字从 ones 中去除。
3. 接着，将当前元素与 twos 做与运算，然后与 ones 做异或运算。这两步的目的是在 twos 中保留出现两次的数字，而将只出现一次的数字从 twos 中去除。
4. 最终，ones 中存储的就是只出现一次的数字。

代码实现

以下是使用Java实现的解决方案：

public class SingleNumberII {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            ones = (ones ^ num) & ~twos;
            twos = (twos ^ num) & ~ones;
        }
        return ones;
    }
}

算法分析

• 时间复杂度：遍历一次数组，时间复杂度为 O(N)，其中 N 是数组的长度。
• 空间复杂度：使用了常量级的额外空间，空间复杂度为 O(1)。

示例和测试

你可以使用以下代码来测试算法：

public class Main {
    public static void main(String[] args) {
        SingleNumberII solution = new SingleNumberII();
        int[] nums = {2, 2, 3, 2};

        int single = solution.singleNumber(nums);
        System.out.println("只出现一次的数字是：" + single);
    }
}

总结

寻找只出现一次的数字II问题是一个经典的位运算问题。通过位运算的技巧，我们能够高效地解决这个问题。熟练掌握位运算的应用场景，能够帮助我们解决更多类似的问题。