136. 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:

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

Example 2:

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

Solution:

两遍遍历的方法:

// Time:O(n^2), Space:O(1);
class Solution {
 public:
  int singleNumber(vector<int> &nums) {
    if (nums.size() == 1) return nums[0];
    int n = nums.size();
    for (int i = 0; i < n; i++) {
      int ok = 0;
      for (int j = 0; j < n; j++) {
        if (i == j) continue;
        if (nums[i] == nums[j]) {ok = 1; break;}
      }
      if (!ok) return nums[i];
    }
    return 0;
  }
};

异或操作的做法,

// ^异或操作, 两次异或同一数, 结果相同
// Time:O(n), Space:O(1);
class Solution {
 public:
  int singleNumber(vector<int> &nums) {
    int ans = 0;
    for (int i = 0; i < nums.size(); i++) {
      ans ^= nums[i];     // 4 ^ 2 ^ 2 ^ 3 ^ 3 = 4 ^ 0 = 4
    }
    return ans;
  }
};

a ^ b   // 如果a, b相同, 则0; 如果不同则1

将两两相同的数字合并, 运算后只得到剩下的一个single number