专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

一网友发文说曾经的985，就因为买个房，一辈子全毁了，亏了几百万，上班完全没动力。

面对这样的困境，许多人可能会感到绝望和无助，然而赚钱是努力，买房是投机，投机有输有赢，亏了很正常。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第137题：只出现一次的数字 II。

问题描述

来源：LeetCode第137题

难度：中等

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

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

示例1：

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

示例2：

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

  • 1 <= nums.length <= 3 * 10^4

  • -2^31 <= nums[i] <= 2^31 - 1

  • nums中，除某个元素仅出现一次外，其余每个元素都恰出现三次

问题分析

这题解法比较多，我们来看一种比较高效的解法。

按照题意的要求，我们定义一种运算如果某个数出现 3 次，通过这种运算就让他的结果变成 0 ，也就是说周期是 3 。每个数都会有下面几种状态

1，出现 0 次

2，出现 1 次

3，出现 2 次

4，出现 3 次

因为周期是 3 ，当出现 3 次的时候可以认为出现了 0 次，也就是下面几种状态

1，出现 0 次

2，出现 1 次

3，出现 2 次

看到这里其实大家已经想到了，这不就是传说中的 3 进制吗。

在二进制中一个位置要么是 1 要么是 0 ，只能表示一种状态，如果要表示 3 种状态我们可以使用两位数字来表示

我们可以选择

1，00表示出现0次

2，01表示出现1次

3，10表示出现2次

但这里好像没有出现 3 次的，其实上面已经说了，出现 3 次的可以认为是出现 0 次。对于每一个数字，如果是 0 我们就不用了管他，只有是 1 的时候状态才会改变。

对于上面公式的推导需要数电方面的知识，需要了解卡诺图，具体可以看下 第三章位运算。也可以使用卡诺图化简法对它进行化简。

JAVA：

public int singleNumber(int[] nums) {
    int a = 0, b = 0;
    for (int c : nums) {
        // 防止a的值修改，在计算b的时候有影响，
        // 这里在b计算完之后再对a赋值
        int tmpa = ~a & b & c | a & ~b & ~c;
        b = ~a & ~b & c | ~a & b & ~c;
        a = tmpa;
    }
    return b;
}

C++：

public:
    int singleNumber(vector

  &nums) {         int a = 0, b = 0;         for (int c: nums) {             // 防止a的值修改，在计算b的时候有影响，             // 这里在b计算完之后再对a赋值             int tmpa = ~a & b & c | a & ~b & ~c;             b = ~a & ~b & c | ~a & b & ~c;             a = tmpa;         }         return b;     }

Python：

def singleNumber(self, nums: List[int]) -> int:
    a, b = 0, 0
    for c in nums:
        # 防止a的值修改，在计算b的时候有影响，
        # 这里在b计算完之后再对a赋值
        tmpa = ~a & b & c | a & ~b & ~c
        b = ~a & ~b & c | ~a & b & ~c
        a = tmpa
    return b

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。