当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

LeetCode[位运算] - #137 Single Number II

发表于: 2015-07-19   作者:Cwind   来源:转载   浏览:
摘要: 原题链接:#137 Single Number II  要求: 给定一个整型数组,其中除了一个元素之外,每个元素都出现三次。找出这个元素 注意:算法的时间复杂度应为O(n),最好不使用额外的内存空间   难度:中等   分析: 与#136类似,都是考察位运算。不过出现两次的可以使用异或运算的特性 n XOR n = 0, n XOR 0 = n,即某一

要求:

给定一个整型数组,其中除了一个元素之外,每个元素都出现三次。找出这个元素

注意:算法的时间复杂度应为O(n),最好不使用额外的内存空间

 

难度:中等

 

分析:

与#136类似,都是考察位运算。不过出现两次的可以使用异或运算的特性 n XOR n = 0, n XOR 0 = n,即某一位上出现偶数次1将该位置为0,出现奇数次1将该位置为1,这样扫一遍数组即可得到结果。

 

类似的,对于本题出现三次的情况,我们需要构造一个与异或类似的运算,使某一位出现三次1时置为0,出现3n+1次1时置为1。取三个整型值ones, twos, threes,均初始化为0,分别用于记录某一位出现1的次数。为简单起见,设输入数组M = {1,1, ... 1}, M中元素个数为m,则对于每一个输入项M[i],令:

 

twos = twos | ones & M[i]

ones = ones ^ M[i]

threes = ones & threes

ones = ones & ~threes // 当threes为1时将ones和twos置为0

twos = twos & ~threes

 

故m=3n时,threes = 1, m=3n+1时,ones = 1。

 

解决方案:

Java - 248ms

public int singleNumber(int[] A) {
        if(A.length==0) {
            return 0;
        }
        int ones=0, twos=0, threes=0;
        for (int i=0;i

 简单测试程序

 

LeetCode[位运算] - #137 Single Number II

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
问题来源:Single Number II 问题描述:给定一个整数数组,除了一个整数出现一次之外,其余的每一个
Question: Given an array of integers, every element appears three times except for one. Find
题目如下: 题目解析: 给定一个含有n个整数的数组,该数组中每个元素出现过两次,唯独有一个出现过
Question: Given an array of integers, every element appears twice except for one. Find that s
位运算 位运算   位运算时把数字用二进制表示之后,对每一位上0或者1的运算。   理解位运算的第
题目: int func(unsigned int i) { Unsigned int temp=i Temp=(temp & 0x55555555)+((temp & 0xaaa
一、六种位运算符: & 按位与 | 按位或 ^ 按位异或 ~ 取反 << 左移 >> 右移 将int型变
解法一: 人类需要O(n)去解决问题,于是普罗米修斯不管三七二十一就偷来了Hash... Python里面内置的d
一、简介 Java中所有的数据都是以二进制数据的形式进行计算的,即如果有一个int型变量,要采用位运
位运算 二进制 所谓的二进制就是逢二进一(0,1),因为使用二进制只有0,1 俩个数,简单,易于电子方
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号