Single Number

来看这个题,https://oj.leetcode.com/proble…

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?

第一反应就是异或,唯一需要确认的就是异或运算是否支持交换律,通过这里,http://longzxr.blog.sohu.com/1…,确认了支持,那么答案就很简单了:

class Solution {
public:
    int singleNumber(int A[], int n) {
        int r = 0;
        for (int i = 0; i < n; i++) {
            r ^= A[i];
        }
        return r;
    }
};

One thought on “Single Number

  1. Pingback: Single Number II | ZRJ

Leave a Reply

Your email address will not be published. Required fields are marked *