首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
V2EX  ›  分享创造

分享一道让你拍案叫绝的算法题

  •  
  •   CoderOnePolo · 93 天前 · 3749 次点击
    这是一个创建于 93 天前的主题,其中的信息可能已经有所发展或是发生改变。

    这是一道看完答案会觉得很简单,但做之前很难想到答案的题目!!!

    不信?

    Let us go !

    题目描述

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

    说明:

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

    示例 1:

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

    示例 2:

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

    题目解析

    根据题目描述,由于加上了时间复杂度必须是 O(n),并且空间复杂度为 O(1)的条件,因此不能用排序方法,也不能使用 map 数据结构。

    小吴想了一下午没想出来,答案是使用 位操作 Bit Operation 来解此题。

    将所有元素做异或运算,即 a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n],所得的结果就是那个只出现一次的数字,时间复杂度为 O(n)。

    异或

    异或运算 A ⊕ B 的真值表如下:

    | A | B | ⊕ | |:------------- |:---------------:| -------------:| | F | F | F | | F | T | T | | T | F | T | | T | T | F |

    动画演示

    进阶版

    有一个 n 个元素的数组,除了两个数只出现一次外,其余元素都出现两次,让你找出这两个只出现一次的数分别是几,要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

    示例 :

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

    题目再解析

    根据前面找一个不同数的思路算法,在这里把所有元素都异或,那么得到的结果就是那两个只出现一次的元素异或的结果。

    然后,因为这两个只出现一次的元素一定是不相同的,所以这两个元素的二进制形式肯定至少有某一位是不同的,即一个为 0,另一个为 1,现在需要找到这一位。

    根据异或的性质 任何一个数字异或它自己都等于 0,得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。

    再然后,以这一位是 1 还是 0 为标准,将数组的 n 个元素分成两部分。

    • 将这一位为 0 的所有元素做异或,得出的数就是只出现一次的数中的一个

    • 将这一位为 1 的所有元素做异或,得出的数就是只出现一次的数中的另一个。

    这样就解出题目。忽略寻找不同位的过程,总共遍历数组两次,时间复杂度为 O(n)。

    动画再演示

    End

    本题的基础版来源于 LeetCode 第 136 号问题:只出现一次的数字。虽然题目难度是 简单,但解法真的很巧妙。感兴趣的同学可以根据思路去回答一下: https://leetcode-cn.com/problems/single-number/

    预防杠精,注: 思路是否拍案叫绝与此前在剑指 offer 上是否看到过此题并没有关系

    原文:一道让你拍案叫绝的算法题

    35 回复  |  直到 2019-02-03 00:39:42 +08:00
        1
    Kaiv2   93 天前
    这让我想到了一道面试题,给狗狗喂药的
        2
    CoderOnePolo   93 天前 via iPhone
    @Kaiv2 100 只🐶,两瓶毒药那种吗?
        3
    rrfeng   93 天前 via Android
    题目读了一半就知道是异或了…

    虽然我不写算法但是看得多了套路上了
        5
    hadoop   93 天前 via Android
    这…不是常用套路吗
        6
    aheadlead   93 天前 via iPhone   ♥ 1
        7
    Sanko   93 天前 via Android
    leetcode 刷过这个
        8
    zhujinliang   93 天前 via iPhone
    如果题目是重复出现的数字可以重复奇数次,怎么做呢?
        9
    lshang   93 天前 via Android
    @zhujinliang 重复奇数次不是跟现在一样么,最终会剩下一个数字
        10
    mathzhaoliang   93 天前
    @lshang 不对。你试试 [1 ,1 ,1 , 0] 这个最简单的例子。
        11
    auv1107   93 天前
    虽然现在看是一道集齐普通的算法题,但当第一次看到时确实有一种拍案叫绝、醍醐灌顶之感。
        12
    VoidChen   93 天前
    看了开头我就知道是异或了,这不能说巧妙,只是很多人没想起异或有这样的特性
        13
    sagaxu   93 天前 via Android
    十年前就见过的套路
        14
    urmyfaith   93 天前
    走过的路都是套路?
        15
    felixlong   93 天前 via Android
    这样的题目只能自娱自乐啦。就像孔乙己问茴字的四种写法一样。
        16
    Amit   93 天前
    动态图片是用什么工具做的?
        17
    est   93 天前
    如果一个出现 3 次,其他的都出现 5 次呢。 /狗头
        18
    stone666   93 天前
    让我想起了 BitMap
        19
    jmc891205   93 天前 via iPhone
    写长文也就算了
    居然还做了图片
    lz 工作不饱和呀~ txtx
        20
    ayase252   93 天前 via iPhone
    用设计数字电路的办法有通解
        21
    woodensail   93 天前
    [1e9,1e10,1e11]
    来演示一下
        22
    thedrwu   93 天前 via Android
    大家一起 xor 一下不就解决了吗。。不需要额外空间。
        23
    thedrwu   93 天前 via Android
    呃…只看完题目描述就抢答了。没看楼主已经给出了答案
        24
    duanluray   93 天前
    leetcode 刷过,HW 的机试也做过
        25
    Kaiv2   93 天前 via Android
    @CoderOnePolo 1000 瓶毒药 1 瓶有毒,喂给 10 只狗狗,猜哪瓶有毒
        26
    alpenstock   92 天前
    喵~
        27
    qiutianaimeili   92 天前
    之前见过
        28
    XuanFei990   92 天前
    都是套路。。。

    之前刷了一个重复奇数次的,,最快的算法也是这种逻辑运算组合出来的。。
        29
    susecjh   91 天前 via Android
    就这?
        30
    YingJie   91 天前 via Android
    好像是 leetcode 简单级别的吧?
        31
    northernlights   91 天前
    我想知道这样的动画演示是怎么制作出来的,谁能告诉我?
        32
    smilev587   91 天前
    是我语文学的不好么? 为啥后面你写的内容我都读不懂?
        33
    jsp   91 天前
    其实位运算的各种性质都挺奇特的,很少回去留意。。 感谢楼主分享。
        34
    xieincz   76 天前
    @Kaiv2 二分法就可以了
        35
    Kaiv2   75 天前 via Android
    @xieincz 嗯,这一题的关键点实在怎么区分那瓶毒药,显然只有十只狗,不确定那瓶有毒,不能靠运气测试。原题中描述需要在 4 小时内确定哪瓶有毒,毒药发作需要两小时。这里解题很巧妙的是用二进制方式来识别毒药。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2407 人在线   最高记录 4385   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 19ms · UTC 14:44 · PVG 22:44 · LAX 07:44 · JFK 10:44
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1