当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.136.Single Number

LeetCode.136.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?


解题过程

这道题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代码


上一篇 LeetCode.543.Diameter of Binary Tree

下一篇 LeetCode.442.Find All Duplicates in an Array

阅读
294
阅读预计1分钟
创建日期 2018-01-22
修改日期 2018-01-24
类别
百度推荐