微信公众号：路人zhang
网站救助计划

1.为阅读体验，本站无任何广告，也无任何盈利方法，站长一直在用爱发电，现濒临倒闭，希望有能力的同学能帮忙分担服务器成本


2.捐助10元及以上同学，可添加站长微信lurenzhang888，备注捐助，网站倒闭后可联系站长领取本站pdf内容


3.若网站能存活下来，后续将会持续更新内容

当前位置： 算法 > 剑指offer > 剑指offer 56-2. 数字中出现的次数

剑指offer 56-2. 数字中出现的次数

题目描述

在一个数组 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

题解

(位运算) O(32n)

枚举每个数的每一位，用 one 记录每一位 1 出现的个数，如果 one % 3 == 1 说明答案中的当前位是 1，否则 one % 3 == 0 说明答案中的当前位不是 1，只有这两种情况，因为剩下的数都出现了三次，只有答案是出现一次的数字，所以处理完每一位之后就可以得到答案，这个方法还是比较好理解的。

时间复杂度

枚举数字的每一位，每个数字 32 位，总共 n 个数，所以时间复杂度为 O(32n)，但这个算法其实不是 O(n) 的，假设 n 的范围是 10^6，则 logn < 32 ，所以此算法时间复杂度是大于 O(nlogn) 的。

空间复杂度

O(1)

C++ 代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; i ++ ) {
            int one = 0;
            for (auto x : nums)
                if (x >> i & 1)
                    one ++ ;
            if (one % 3 == 1) res += (1 << i);
        }
        return res;
    }
};

Java 代码

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i ++ ) {
            int one = 0;
            for (int x : nums) {
                if ((x >> i & 1) == 1) {
                    one++;
                }
            }
            if (one % 3 == 1) {
                res += (1 << i);
            }
        }
        return res;
    }
}

Python 代码

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):
            one = 0
            for x in nums:
                if (x >> i & 1) == 1:
                    one += 1
            if one % 3 == 1:
                res += (1 << i)
        return res

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer