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

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

  •  
  •   CoderOnePolo · 2019-01-16 11:19:31 +08:00 · 5544 次点击
    这是一个创建于 1899 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    不信?

    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
    Kaiv2
        1
    Kaiv2  
       2019-01-16 11:35:29 +08:00
    这让我想到了一道面试题,给狗狗喂药的
    CoderOnePolo
        2
    CoderOnePolo  
    OP
       2019-01-16 11:54:14 +08:00 via iPhone
    @Kaiv2 100 只🐶,两瓶毒药那种吗?
    rrfeng
        3
    rrfeng  
       2019-01-16 11:58:51 +08:00 via Android
    题目读了一半就知道是异或了…

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

    之前刷了一个重复奇数次的,,最快的算法也是这种逻辑运算组合出来的。。
    susecjh
        29
    susecjh  
       2019-01-18 07:56:06 +08:00 via Android
    就这?
    YingJie
        30
    YingJie  
       2019-01-18 08:43:56 +08:00 via Android
    好像是 leetcode 简单级别的吧?
    northernlights
        31
    northernlights  
       2019-01-18 10:04:05 +08:00
    我想知道这样的动画演示是怎么制作出来的,谁能告诉我?
    smilev587
        32
    smilev587  
       2019-01-18 10:46:15 +08:00
    是我语文学的不好么? 为啥后面你写的内容我都读不懂?
    jsp
        33
    jsp  
       2019-01-18 11:35:40 +08:00
    其实位运算的各种性质都挺奇特的,很少回去留意。。 感谢楼主分享。
    r6cb
        34
    r6cb  
       2019-02-02 21:32:53 +08:00
    @Kaiv2 二分法就可以了
    Kaiv2
        35
    Kaiv2  
       2019-02-03 00:39:42 +08:00 via Android
    @xieincz 嗯,这一题的关键点实在怎么区分那瓶毒药,显然只有十只狗,不确定那瓶有毒,不能靠运气测试。原题中描述需要在 4 小时内确定哪瓶有毒,毒药发作需要两小时。这里解题很巧妙的是用二进制方式来识别毒药。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4032 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 10:14 · PVG 18:14 · LAX 03:14 · JFK 06:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.