[leetcode] Single Number


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?

tag: hash table, bit manipulation

异或有一个很神奇的属性,可以把奇数个元素挑出来。本质是因为:
1. 异或具有交换性 A^B = B^A
2. 0与一个数异或等于它本身

所以该数列中,可以看成把出现两次的元素交换在临近位置,异或之后为0,最后剩下0与出现一次的元素异或,为该元素本身。

一次AC。

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

Selection_027

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.