LeetCode - 数组中的单一数_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > LeetCode - 数组中的单一数

LeetCode - 数组中的单一数

 2015/3/20 9:49:13  Cwind  程序员俱乐部  我要评论(0)
  • 摘要:原题链接:#136SingleNumber要求:给定一个整型数组,其中除了一个元素之外,每个元素都出现两次。找出这个元素注意:算法的时间复杂度应为O(n),最好不使用额外的内存空间难度:中等分析:题目限定了线性的时间复杂度,同时不使用额外的空间,即要求只遍历数组一遍得出结果。由于异或运算nXORn=0,nXOR0=n,故将数组中的每个元素进行异或运算即可得到结果解决方案:Java-245mspublicintsingleNumber(int[]A){if(A.length==0)
  • 标签:数组

原题链接:#136?Single Number

要求:

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

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

难度:中等

分析:

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

解决方案:

Java - 245ms

class="java" name="code">    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

简单测试程序

上一篇: session生命周期 下一篇: 没有下一篇了!
发表评论
用户名: 匿名