【Java题解】剑指 Offer 56 - II. 数组中数字出现的次数 II

本文主要是介绍【Java题解】剑指 Offer 56 - II. 数组中数字出现的次数 II，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

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

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

方法一：
使用位运算以及有限状态自动机（leetcode上的大佬这么叫的）
以下题解参考自：leetcode题解

1. 对于二进制来说，多个数字的二进制表示中，如果让相同位的0，1加起来计数后，对重复的数字个数（这里是3）进行求余，那么就可以消除重复的数字，只剩下不重复的数字。（其实就是把重复的数字给置为0了，那么按位加起来的数字就是哪一个不重复的数字。）如下图：
   
2. 如何实现？需要用到有限状态自动机。
   各二进制位的 位运算规则相同 ，因此只需考虑一位即可。由于是3个重复数字，那么可以有00 01 10三个状态。并且来回进行切换。
3. 可以使用两个数字分别记录上面三个状态中的低位和高位。ones twos，这样操作的原因是：方便计算，ones twos只需要根据对方的值进行变更数字0 1就好了。
4. 推导

计算 ones 方法：

if two == 0:
    if n == 0:
        one = one
    if n == 1:
         one = ~one
    if two == 1:
        one = 0

引入 异或运算 ，可将以上拆分简化为：

if two == 0:
     one = one ^ n
if two == 1:
    one = 0

引入 与运算 ，可继续简化为：

one = one ^ n & ~two

计算 twos 方法：
同理可得：
two = two ^ n & one（这个式子和大佬题解的不同，但是两个式子都能得出正确答案）

代码：

class Solution {
    public int singleNumber(int[] nums) {
        // 使用二进制的位运算
        int ones = 0, twos = 0;
        // ones : 记录00 01 10 的低位上的位数。 即00 01
        // twos : 记录高位上的数字 即10
        for (int i = 0; i < nums.length; i++) {
            ones = ones ^ nums[i] & ~twos;
            twos = twos ^ nums[i] & ones; 
        }
        // 最终要返回的是状态为00 01的结果，所以是ones
        return ones;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

这篇关于【Java题解】剑指 Offer 56 - II. 数组中数字出现的次数 II的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！