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

LeetCode[位运算] - #136 数组中的单一数

发表于: 2015-03-20   作者:Cwind   来源:转载   浏览:
摘要: 原题链接:#136 Single Number 要求: 给定一个整型数组,其中除了一个元素之外,每个元素都出现两次。找出这个元素 注意:算法的时间复杂度应为O(n),最好不使用额外的内存空间 难度:中等 分析: 题目限定了线性的时间复杂度,同时不使用额外的空间,即要求只遍历数组一遍得出结果。由于异或运算 n XOR n = 0, n XOR 0 = n,故将数组中的每个元素进

原题链接:#136 Single Number

要求:

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

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

难度:中等

分析:

题目限定了线性的时间复杂度,同时不使用额外的空间,即要求只遍历数组一遍得出结果。由于异或运算 n XOR n = 0, n XOR 0 = n,故将数组中的每个元素进行异或运算即可得到结果

解决方案:

Java - 245ms

    public int singleNumber(int[] A) {
        if(A.length==0) {
            return 0;
        }
        int singleNum = A[0];
        for(int i=1; i<A.length; i++) {
            singleNum = singleNum ^ A[i];
        }
        return singleNum;
    }

简单测试程序

Python - 93ms

    def singleNumber(self, A):
        singleNum = A[0]
        for i in range(1,A.__len__()):
            singleNum = singleNum ^ A[i]
        return singleNum

简单测试程序

LeetCode[位运算] - #136 数组中的单一数

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
位运算 二进制 所谓的二进制就是逢二进一(0,1),因为使用二进制只有0,1 俩个数,简单,易于电子方
//Java中的位运算 /*计算机由复杂电子元器件构成,一个电子元器件有带电和不带电的两种状态,1和0
位运算 位运算   位运算时把数字用二进制表示之后,对每一位上0或者1的运算。   理解位运算的第
题目: int func(unsigned int i) { Unsigned int temp=i Temp=(temp & 0x55555555)+((temp & 0xaaa
一、六种位运算符: & 按位与 | 按位或 ^ 按位异或 ~ 取反 << 左移 >> 右移 将int型变
一、简介 Java中所有的数据都是以二进制数据的形式进行计算的,即如果有一个int型变量,要采用位运
原理 在Linux文件系统中,一个用户对文件或目录所拥有的权限分为三种:”可读”、”可写”和”可执
数据库采用1,2,4,8,16.....等用数字标识的状态字段可以进行累加,对存在的几种状态进行组合,从而可形
原理 在Linux文件系统中,一个用户对文件或目录所拥有的权限分为三种:”可读”、”可写”和”可执
原理 在Linux文件系统中,一个用户对文件或目录所拥有的权限分为三种:”可读”、”可写”和”可执
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号