Leetcode 题目解析之 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?

对于出现2次的数字，用异或。因为“相异为1”，所以一个数字异或本身为0，而0异或0仍为0， 一个数字异或0仍为这个数字。

代码语言：javascript复制

0 ^ 0 = 0 
n ^ 0 = n 
n ^ n = 0

代码语言：javascript复制

    public int singleNumber(int[] nums) {
        int n = 0;
        for (int i : nums) {
            n ^= i;
        }
        return n;
    }

algorithm element find runtime using

0 人点赞