LeetCode_136_SingleNumber

136. Single Number

Total Accepted: 122616 Total Submissions: 248345 Difficulty: Medium

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?

题目分析:

给定一个数组,其中每个元素都重复了两次,只有一个元素出现了一次,找出这个元素.

要求T(n) = O(n),并且不开辟新的内存空间(C++无法做到，姑且认为 S(n) = O(1)).

解:

XOR相关知识：

A^A = 0

A^0 = A

A^A^B = B

且XOR满足交换律和分配律

Solution：

int singleNumber(vector<int>& nums)
{
    for (int i = 1; i < nums.size(); i++)
        nums[0] ^= nums[i];
    return nums[0];
}

T(n) = O(n)

S(n) = O(1)

LeetCode_136_SingleNumber

原文：http://www.cnblogs.com/HellcNQB/p/5361573.html