【LeetCode】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?

给一个整数数组，里面的元素中除了一个元素外，其余每一个元素都出现两次，找出那个只出现一次的整数。

要求：代码要求在线性时间内运行，最好是能够实现不需要使用其它空间。

分析

对整个数组每个元素依次使用亦或运算，最终留下的那个数就是Single Number。

代码

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