【每日leetcode】8.只出现一次的数字

对异或运算符的应用，非常有趣 ——leetcode此题热评

前言

哈喽，大家好，我是一条。 糊涂算法，难得糊涂。 生命不息，刷题不止！

Question

难度：简单

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

Solution

一条开始用hashSet做的，好家伙，足足9ms 后来看了一下原来有异或运算这么神奇的方法

异或运算满足以下规律：

1. 交换律：a ^ b ^ c = a ^ c ^ b
2. 任何数于0异或为任何数 0 ^ n = n
3. 相同的数异或为0: n ^ n = 0

int a[] ={2,3,2,4,4};
2 ^ 3 ^ 2 ^ 4 ^ 4= 2 ^ 2 ^ 4 ^ 4 ^ 3 = 0 ^ 0 ^3 = 3

Code

所有leetcode代码已同步至github https://github.com/lbsys/leetcode/tree/master/src/leetcode/editor/cn 欢迎star

class Solution {
    public int singleNumber(int[] nums) {
        int result=0;
        for (int i = 0; i < nums.length; i++) {
           result =nums[i]^result;
        }
        return result;
    }
}

Result

复杂度分析

• 时间复杂度：O(N)