Java教程

【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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!