• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

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

开发技术 开发技术 3周前 (09-09) 22次浏览

题目描述

在一个数组 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)
链接:https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof

方法一:map

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int, int> nums_map;
        for(int num : nums)
            nums_map[num]++;
        for(auto &key : nums_map)
            if(key.second == 1)
                return key.first;
        return 0;
    }
};

这个方法不用多说,时间复杂度和空间复杂度均为(O(n))

方法二:位运算

基本思路:int值为32位,由于仅有一个数字只出现了1次,其余数字均出现了3次,统计每一位上1出现的次数,并对3求余,可得目标数字的二进制表示。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if(nums.empty())    return 0;
        int result = 0;
        // 对32位分别统计1出现的次数
        for(int i = 0; i < 32; i++) {
            int count = 0;
            int index = 1 << i;
            // 遍历数组中的每个数字,统计第i位上是否为1
            for(int num : nums) {
                if((index & num) != 0)
                    count++;
            }
            // 若count对3求余结果为1,则目标数字的该位为1,使用按位或运算记入result
            if(count % 3 == 1)
                result |= index;
        }
        return result;
    }
};

时间复杂度(O(n)),空间复杂度(O(1))

方法三:位运算进阶

方法二在时间复杂度和空间复杂度上都已经很好了,但还有加速的空间,由于方法二中对每一个数字都需要进行32次统计,则时间复杂度(O(n))有常系数32,思考办法将常系数32降低。

  • 我们的目的没有改变,仍然是统计第(i)位上1出现的次数(n_i),准确的说是统计((n_i% 3))
  • 每一位上1出现的次数对3的余数可以表示为0,1,2三种情况,但是3中情况无法使用一位二进制数字来表示,因此我们需要扩充至两位二进制数字00 01 10 ,最后得到64位的结果的形式如下:
    00 01 10 ... 00 10 ...
  • low表示低位,high表示高位,真值表如下:
high low digit high low
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0
  • 低位的求值方法为:
if(high == 0)
    if(digit == 0)
        low = 0;
    else
        low = 1;
else
    low = 0;

使用异或运算表达:

if(high == 0)
    low = (low ^ digit);
else
    low = 0;

稍加整理:

low = (low ^ digit) & (~high)
  • 高位的求值方法为:
    在计算高位之前,要考虑到此时的低位已经是经过运算之后的新的低位
if(low == 0)
    if(digit == 0)  // 对应真值表第三行和第五行
        high = high;
    else            // 对应真值表第七行和第八行
        high = ~high;
else	            // 对应真值表第四行和第六行
    high == 0;

使用异或运算表达:

if(low == 0)
    high = (high ^ digit);
else
    high = 0;

稍加整理:

high = (high ^ digit) & (~low);

最终代码实现如下:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int low = 0;
        int high = 0;
        for(int num : nums) {
            low = (low ^ num) & (~high);
            high = (high ^ num) & (~low);
        }
        return low;
    }
};

时间复杂度(O(n)),空间复杂度(O(1))


喜欢 (0)