微信公众号:路人zhang
扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 算法 > 剑指offer > 剑指offer 56-2. 数字中出现的次数
本文链接:https://www.mianshi.online/2790.html

题目描述

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