剑指 Offer 56 – II. 数组中数字出现的次数 II

剑指offer最优解免费

本问题对应的 leetcode 原文链接：剑指 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

解题思路

视频讲解直达：本题视频讲解

代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int[] res = new int[32];
        int m = 1;
        int sum = 0;
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < nums.length; j++){
                if((nums[j] & m) != 0){
                    res[i]++;
                }
            }

            res[i] = res[i] % 3;
            sum = sum + res[i] * m;
            m = m << 1;
        }

        return sum;
    }
}

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

Python

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = [0] * 32
        m = 1
        sum = 0
        for i in range(32):
            for j in range(len(nums)):
                if (nums[j] & m) != 0:
                    res[i] += 1
            res[i] %= 3
            sum += res[i] * m
            m <<= 1
        return sum

C++

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> res(32, 0);
        unsigned int m = 1;
        int sum = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if ((nums[j] & m) != 0) {
                    res[i]++;
                }
            }
            res[i] %= 3;
            sum += res[i] * m;
            m <<= 1;
        }
        return sum;
    }
};

Go

func singleNumber(nums []int) int {
    res := make([]int, 32)
    m := 1
    sum := 0
    for i := 0; i < 32; i++ {
        for j := 0; j < len(nums); j++ {
            if (nums[j] & m) != 0 {
                res[i]++
            }
        }
        res[i] %= 3
        sum += res[i] * m
        m <<= 1
    }
    return sum
}

JS

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let res = new Array(32).fill(0);
    let m = 1;
    let sum = 0;
    for (let i = 0; i < 32; i++) {
        for (let j = 0; j < nums.length; j++) {
            if ((nums[j] & m) != 0) {
                res[i]++;
            }
        }

        res[i] = res[i] % 3;
        sum = sum + res[i] * m;
        m = m << 1;
    }

    return sum;
};

剑指offer题解