您当前的位置: 首页 >  leetcode

星拱北辰

暂无认证

  • 0浏览

    0关注

    1205博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【LeetCode】查找只出现一次的数字算法

星拱北辰 发布时间:2020-02-20 19:39:01 ,浏览量:0

题目要求

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

(LeetCode136也就是这么个题吧,简单题,要求是最好写出线性的时间复杂度和O(1)的空间复杂度)

分析

首先很容易想的就是开一个数组计数,但算法效率肯定不好。 还可能用哈希什么的去做,线性的空间能保证吗? …… 其实这问题本质上是考察 按位异或 的位运算符的。

怎么说? 学过离散数学我们知道,异或是说,同则取0,异则取1。 按位异或就是按照二进制的表示,两个数每一位同则取0,异则取1。 异或也有交换律:a ^ b = b ^ a,所以顺序无所谓的。 既然其他数都是出现两次,那我们就可以认为遍历结束后的时候,每个两两相同的数值对异或后都是0了,剩下的是那个落单的。 怎么让结果就是落单的呢? 还得从0身上下手: a ^ 0 = a 所以说,只要初值设成0的话,遍历一趟数组,逐一异或,最终结果就是出现一次的数。

Java编程实现
class Solution {
    public int singleNumber(int[] nums) {
        int n = 0;
        for (int i : nums) {
            n ^= i;
        }
        return n;
    }
}
关注
打赏
1660750074
查看更多评论
立即登录/注册

微信扫码登录

0.0666s