专栏首页小浩算法漫画:神奇的找出只出现一次的数字!

漫画:神奇的找出只出现一次的数字!

01

题目分析

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

说明:

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

示例 1:

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

示例 2:

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

我们拿到题目的一瞬间,用脚趾头都能想到可以通过hash表进行暴力求解。因为题目中已经告知我们除了目标元素之外,其他元素都只出现两次。所以我们可以用一个很简单的逻辑“如果出现第一次就放入map中,如果出现第二次就将其删除”,最终map中剩下的唯一一个元素,就是我们要找的目标元素。该种解法过于简单,直接上代码:

func singleNumber(nums []int) int {
    m := make(map[int]int)
    for _, v := range nums {
        if _, exist := m[v]; exist {
            //如果元素存在就删除
            delete(m, v)
        } else {
            //如果不存在将其放入,值随意
            m[v] = 1
        }
    }
    for k, _ := range m {
        return k
    }
    //在当前题目限制条件下,这一行应该是跑不到的
    return 0
}

但是很明显,这种解法并不是我们想要的。因为这种情况下,我们使用到了额外空间。那我们如何在不使用额外空间的前提下,来完成这道题目呢,下面是我们的思考过程。

02

题目图解

首先我们回忆一下,我们知道的按位异或(xor)运算。(这是专门给基础薄弱的道友准备的,懂的可以自行跳过....)

异或(xor)是一个数学运算符,它应用于逻辑运算。异或的数学符号为“⊕”,计算机符号为“xor”。在异或中,如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。(其实很好记忆,就是男的和女的才能生出孩子,如果两个男的或两个女的,那就不行...)

而异或运算,满足于交换律其实也很好理解,男的和女的,女的和男的,其实都可以生出孩子..

注意:这里需要强调的是,异或属于二进制运算。因为真的有人可能会问我"你说a,b不同则结果为1,那为啥我在编译器里计算3^1,最终结果却是2"这样的问题。

在上面的知识基础上,我们只需要将所有数字按照顺序做异或运算,最终剩下的数字就是唯一的数字。

因为任意两个相同的数字进行异或,结果为0

a ^ a = 0

而0和任意数字进行异或,又等于其本身。比如 10 ^ 0 ,如图:

03

Go语言示例

分析完毕,则代码自成:

func singleNumber(nums []int) int {
    res := 0
    for _, v := range nums {
        res ^= v
    }
    return res
}

注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过go。算法思想最重要,使用go纯属本人爱好。同时,本系列所有代码均在leetcode上进行过测试运行,保证其严谨性!

本文分享自微信公众号 - 小浩算法(xuesuanfa)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:位运算系列篇(只出现一次的数字)

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

    程序员小浩
  • 漫画:位运算技巧整理汇总+一道被嫌弃的题目

    今天是小浩算法“365刷题计划”第65天。这两天总有人来问我,做公众号赚了多少钱,或者就是怎么能和你一样,2个月就做到7000粉丝。说实话,至少到目前为止,我一...

    程序员小浩
  • 漫画:动态规划系列 第四讲

    在上一篇中,我们通过题目“最长上升子序列”以及"最大子序和",学习了DP(动态规划)在线性关系中的分析方法。这种分析方法,也在运筹学中被称为“线性动态规划”,具...

    程序员小浩
  • 异或(京东2017实习生真题)

    异或运算是常见的二进制运算,给出两个n位二进制数a,b。a异或b的运算依次考虑二进制的每一位,若这一位相同,那么这一位的异或结果就是0,不同就是1。 例如a...

    AI那点小事
  • 不使用额外空间交换2个数据的源代码

      最近做求职笔试题,遇到比较有意思的题目,题目或多或少涉及到《剑指Offer》的思路和知识点,如果不是刷书两遍,估计不会做出来,分享一下互相学习! *****...

    waylon
  • 台阶很高,青蛙跳不跳?

    一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法?

    WindWant
  • LeetCode 1450. 在既定时间做作业的学生人数

    给你两个整数数组 startTime(开始时间)和 endTime(结束时间),并指定一个整数 queryTime 作为查询时间。

    Michael阿明
  • 芋道 Spring Boot SpringMVC 入门

    如果胖友接触 Java Web 开发比较早,那么可能会了解到如下 Web MVC 框架,当年是 Struts2 与 SpringMVC 双雄争霸的年代。甚至说,...

    芋道源码
  • 整理数据时的16个常用Excel函数

    示例:下表D:F列中,如果填充“完成”大于1个,则在G列返回达标,否则返回不达标。

    用户5495712
  • 经验之谈,这16个Excel函数,几乎可以解决80%的数据统计工作!

    在日常工作中,数据统计是工作中最重要的一部分。今天把Excel中最常用的统计函数整理了出来,共16个。为了方便同学们理解,选取的全是贴近应用的示例。

    1480

扫码关注云+社区

领取腾讯云代金券