Single Number II

描述

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析

本题和上一题 Single Number,考察的是位运算。

方法1:创建一个长度为sizeof(int)的数组count[sizeof(int)]count[i]表示在在i位出现的1的次数。如果count[i]是3的整数倍,则忽略;否则就把该位取出来组成答案。

方法2:用one记录到当前处理的元素为止,二进制1出现“1次”(mod 3 之后的 1)的有哪些二进制位;用two记录到当前计算的变量为止,二进制1出现“2次”(mod 3 之后的 2)的有哪些二进制位。当onetwo中的某一位同时为1时表示该二进制位上1出现了3次,此时需要清零。即用二进制模拟三进制运算。最终one记录的是最终结果。

代码1

// Single Number II
// 方法1,时间复杂度O(n),空间复杂度O(1)
public class Solution {
    public int singleNumber(int[] nums) {
        final int W = Integer.SIZE; // 一个整数的bit数,即整数字长
        int[] count = new int[W];  // count[i]表示在在i位出现的1的次数
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < W; j++) {
                count[j] += (nums[i] >> j) & 1;
                count[j] %= 3;
            }
        }
        int result = 0;
        for (int i = 0; i < W; i++) {
            result += (count[i] << i);
        }
        return result;
    }
};

代码2

// Single Number II
// 方法2,时间复杂度O(n),空间复杂度O(1)
public class Solution {
    public int singleNumber(int[] nums) {
        int one = 0, two = 0, three = 0;
        for (int i : nums) {
            two |= (one & i);
            one ^= i;
            three = ~(one & two);
            one &= three;
            two &= three;
        }

        return one;
    }
};

相关题目

results matching ""

    No results matching ""