[LeetCode]136. Single Number(找出数组中单独出现的数)

136. Single Number

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? 您的算法应具有线性运行时复杂性。 你能实现它，而不使用额外的内存？

C++ class Solution { public: int singleNumber(vector<int>& nums) { int length = nums.size(); if(length == 1) return nums[0]; int a = 0; for(int i=0;i<length;i++){ a ^= nums[i];//利用异或性质 对于任何数x，都有x^x=0 ，x^0=x ，a^b=b^a 所以 x^y^x = y } return a; } };

注意：

异或性质1、交换律 (a^b = b^a)2、结合律（即(a^b)^c = a^(b^c)）3、对于任何数x，都有x^x=0，x^0=x 所以 x^y^x = y自己着实没想出来好办法，只好百度了一下，异或很重要…