码疯窝

LeetCode 每日一题 — Single Number

2014/12/16 10:47:55    分类: 日志连载    0人评论 次浏览

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

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

算法分析: 这道题目比较有意思, 拿到题目, 首先想到的肯定是遍历. 如果数不存在. 入栈, 存在第二次, 出栈, 这样的话一次循环搞定.
但题目说不要用额外的空间, 那就不符合要求了, 于是只能通过其它方法来实现, 不用额外空间那肯定就得利用计算了, 出了基本的加减乘除, 我们还有与, 或, 非, 异或, 移位等.
正好异或不就是这个特性么? a ^ a = 0, a ^ 0 = a. 于是代码就变得简单明了了.

Java:

public class Solution {
    public int singleNumber(int[] A) {
        int len = A.length;
        int i = 1;
        int rst = A[0];
        for(; i < len; i++)
            rst ^= A[i];
        return rst;
    }
}

C++:

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        rst = A[0]
        i = 0
        n = len(A)
        for i in range(1, n):
            rst ^= A[i]
        
        return rst

Python:

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        rst = A[0]
        i = 0
        n = len(A)
        for i in range(1, n):
            rst ^= A[i]
        
        return rst
继续查看有关 日志连载的文章

0个访客评论