当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.136.Single Number 数组中只出现一次的数

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


上一篇 LeetCode.543.Diameter of Binary Tree 二叉树的直径

下一篇 LeetCode.442.Find All Duplicates in an Array 数组中所有重复的数

阅读
评论
364
阅读预计1分钟
创建日期 2018-01-22
修改日期 2018-01-24
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论