LeetCode.136.Single Number 数组中只出现一次的数

题目描述

136 Single Number https://leetcode-cn.com/problems/single-number/ https://leetcode.com/problems/single-number/description/ 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?

相似题目

LeetCode.136.Single Number 数组中只出现一次的数 LeetCode.137.Single Number II 数组中只出现一次的数2 LeetCode.260.Single Number III 数组中只出现一次的数3 LeetCode.剑指offer.056.数组中数字出现的次数

解题过程

这道题3年前准备校招时做过，用c++，已经AC了，现在用java再做一遍。 这道题印象很深刻，O(n)时间复杂度且无额外空间开销的做法就是用异或位运算。 所有元素进行异或操作，由于a^a=0，所以出现2次的结果都成0了，而a^0=a，所以最后的结果就是只出现一次的数，即a^b^a = a^a^b = 0^b = b。

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

看了看Solution，给出了好几种解法，用哈希表的，不多说了。 还有用集合的，根据公式2∗(a+b+c)−(a+a+b+b+c)=c，先把数组中元素去重得到集合表示set_of_nums，然后2*sum(set_of_nums)-sum(nums)就是结果。 当然，位运算是最快的，最巧妙的。

GitHub代码

algorithms/leetcode/leetcode/_136_SingleNumber.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_136_SingleNumber.java