Single Number II, Leetcode 解题笔记

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?

题目中要求我们不要用额外空间来实现,也就是O(1)空间复杂度。实现的思路是基于数组的元素是整数,我们通过统计整数的每一位来得到出现次数。我们知道如果每个元素重复出现三次,那么每一位出现1的次数也会是3的倍数,如果我们统计完对每一位进行取余3,那么结果中就只剩下那个出现一次的元素。总体只需要对数组进行一次线性扫描,统计完之后每一位进行取余3并且将位数字赋给结果整数,这是一个常量操作(因为整数的位数是固定32位),所以时间复杂度是O(n)。而空间复杂度需要一个32个元素的数组,也是固定的,因而空间复杂度是O(1)。代码如下:

public int singleNumber(int[] A) {
    int[] digits = new int[32];
    for(int i=0;i<32;i++)
    {
        for(int j=0;j<A.length;j++)
        {
            digits[i] += (A[j]>>i)&1;
        }
    }
    int res = 0;
    for(int i=0;i<32;i++)
    {
        res += (digits[i]%3)<<i;
    }
    return res;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s