LeetCode 30 days Challenge - Day 1

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

Single Number

Given a non-empty 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?

Example 1:

1 2	Input: [2,2,1] Output: 1

Example 2:

1 2	Input: [4,1,2,1,2] Output: 4

题目要求分析：给定非空数组，找到单独出现的元素。

解法：

关键利用异或运算符^，对于异或运算：

结合题目给出除了目标元素外，其余元素各出现两次，不难想到遍历整个数组，逐个将元素进行异或运算，最后剩下的元素即为目标。

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int n : nums) res ^= n;
    return res;
}

Karl