5行位运算,map靠边站——位操作进阶

题目:single-number-ii

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题意:给一个数列,所有的数字都出现了3次,除了某一个只出现一次,请找出只出现一次的这个数。数字都在int范围内。

LeetCode上的一道题,我在牛客上交的。

这道题目看起来很简单,但是深究一下还是有东西可学的。

int范围内的数,妄图开个cnt[i]来记录数字 i 的出现次数是无法编译的,过亿的数无论是空间上还是遍历时间上都很要命。

but,我会map的。于是:

class Solution {
public :
        int singleNumber(int A[], int n) {
            map <int,int> mp;
            int ans;

            for (int i = 0; i < n; i++)
            {
                mp[A[i]]++;
                if (mp[A[i]] == 3)    mp.erase(A[i]);
            }
            for (auto i : mp)    ans = i.first;

            return ans;
        }
};

就这么水过去了~

(由于本篇字数较少我决定插入某梗以凑字数)

然鹅初学算法的同学可能只会最开始那种办法,还不会map,比如半年前的我。

可是这样一道不可多得的好题,自己A出来绝对会快感爆棚!

于是,我决定:去看题解。

无论是数百回复的大佬代码,还是无人问津的偏僻算法,它们都足以稳定快速地AC这道题。久而久之,我浏览了太多优秀的题解,然后,我发现了一个残酷的共同点——

它们都难以看懂。

不精简吗?一行行代码就像一句句诗。

不快速吗?O(n)的复杂度我会乱说?

我问过其中一个题解,问:你不会用map吗?

它说:废话,当然会用。

我问:为什么不用map?逼格不够?

它叹气:不,太慢了。

它意味深长道:优秀的ACM选手不需要STL。(大雾)

我立刻就懂了。

是时候放弃这(算)道(法)题(竞)目(赛)了。

接下来正经来说。

题目中有提到Could you implement it without using extra memory?,这道题主要想教给大家的就是位运算。这里只介绍某一个题解的实现,其他神犇代码就不一一介绍了。

首先,假如题目降低难度,出现次数是两次而不是三次的话,很简单的一个做法所有数异或在一起,到最后的结果就是只出现一次的。

原理:a^a = 0,a^0=a; a^b^c = a^c^b。

第一个,异或,指两个数的二进制位相同则为改0(为假),不同则改为1(为真),比如1100^1010=0110,即12^10=6.故一个数异或它本身,肯定各个二进制位都是一样的,结果就都是0了。

第二个,为什么异或可以有交换律?可以这样理解:把数字a视为二进制串然后竖着写,对,就像列向量一样……b、c也如此,这样行就代表了第几位,异或的时候本来就是同位的才在一起异或,不同位的没什么关系。这样就像一个真值表一样,第一列第二列第三列不管你怎么换顺序,都不会影响第四列最终的真值。

好,那现在升级了,再来谈这道题。

先不给予思考过程地给出:我们将用三个变量。one代表只出现一次的数,two代表出现过两次的数,three则代表已经出现了三次的数。而一旦某数的次数从一次变成两次了,那就从one里把它删去,而加到two里;同理,当它第三次出现时将被从two里删去,加到three里。

具体操作:

int one = 0, two = 0, three;

设t是当前出现的数。

int t = A[i];

t要是还没出现,就会被加进去;要是出现过一次,会同自己异或成0,满足了变两次则删去原理.

one ^= t;

而什么叫出现了三次?就是在one里存在,又在two里存在了!1+2=3.

three = one & two;

此数已经记录在three里了,就要从one和two里删去了。

one &= ~three;
two &= ~three;

好,现在待解决问题只剩two怎么get了。简单翻译就是:one里有的,t也有的,那就是第二次了。

two |= one & t;

梳理一下要注意的就是two要在one之前更新。

class Solution {
public:
    int singleNumber(int A[], int n) {
        int one = 0, two = 0, three;
        for (int i = 0; i < n; i++)
        {
            int t = A[i];
            two |= one & t;
            one ^= t;
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }
};

最后,此处应该有个思考,就是这里one和two毕竟只是变量,是二进制串,而不是vector,所以注定中间会有很多数混杂在一起、分不清的情况。那么怎么证明最终结果的正确性呢?还是那样,每个位的运算和其他位是没什么关系的,给出的数列是多少无非决定了这个位会出现多少次1而已。而1的个数又一定是3k或者3k+1.3k的情况自然都消掉了,3k+1自然到后面会剩出一个1.在理解时关键就是不要把某个数(我称之为行向量)硬生生地不肯拆开,而是以某一位(列向量)的角度去看待。剩下的读者自行体会吧~

最后的最后,我做此题的感受就是,往往最开始我们接触某个题目或者某个算法的时候会很懵逼,想得脑仁直疼也看不懂他代码是做什么用的,但是等你过了几个月又有了一定积累以后,再重新学习这些童年阴影,又总会发现其实都明白了,或者至少多理解了许多。当年不过是自己水平不到而已,硬刚也是徒劳浪费时间。

预告:

上期Fuxey大佬的文章大家收获怎样呢?论完了道,我们也要关注一下术的层面。下周,我们将一起看看codeforces红名是怎样练成的,敬请关注。

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-10-21

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

AI 路上,第一步这么走下去...

算法是描述解决一个问题的步骤,外界给它所指定的数据,然后经过一系列步骤输出一个结果。为了更快更轻量级地解决问题,我们会选择高效精简的结构去实现,这种结构称为数据...

1246
来自专栏java一日一条

有没有一段代码,让你觉得人类的智慧也可以璀璨无比?

Kyle McCormick 在 StackExchange 上发起了一个叫做 Tweetable Mathematical Art 的比赛,参赛者需要用三条推...

873
来自专栏C语言及其他语言

[每日一题]老王赛马

题目描述 赛马是一古老的游戏,早在公元前四世纪的中国,处在诸侯割据的状态,历史上称为“战国时期”。在魏国作官的孙膑,因为受到同僚庞涓的迫害,被齐国使臣救出后,到...

2749
来自专栏C语言及其他语言

[每日一题]矩阵转置(1242)

题目描述 输入N*N的矩阵,输出它的转置矩阵。 输入 第一行为整数N。 接着是一个N*N的矩阵。 输出 转置矩阵 样例输入 2 1 2 1 2 样例输出 1 ...

3449
来自专栏calmound

hdu 1850 Being a Good Boy in Spring Festival

太开心了,这是我第一道自己想出来的利用二进制的做法把博弈做出来的,good!!! 题意:一般的博弈,给你n堆,一次只能取一堆中的任意个,求先手若想获胜有多少可行...

3185
来自专栏数据结构与算法

87. [NOIP2000] 乘积最大

★☆   输入文件:cjzd.in   输出文件:cjzd.out 简单对比 时间限制:1 s   内存限制:128 MB   问题描述 今年是国际...

38810
来自专栏趣学算法

ACM竞赛学习指南(算法工程师成长计划)

6161
来自专栏新智元

邓侃:谷歌Talk to books引爆搜索方式革命

?---- 【新智元导读】昨天,新智元介绍了谷歌的全新搜索工具“Talk to Books”,基于自然语言文本理解,用户能够凭语义而非关键词来实现搜索功能。谷歌...

2916
来自专栏机器之心

机器学习时代的哈希算法,将如何更高效地索引数据

2285
来自专栏WOLFRAM

Mathematica 之微分特征系统

1506

扫码关注云+社区

领取腾讯云代金券