一道能做出来就脚踢BAT的高难度算法题:在元素重复三次的数组中查找重复一次的元素

我们看一道难度很高的查找类算法题,如果你真能在一小时内给出正确的算法和编码,那么你随便在BAT开口年薪一百万都不算过分。我们先看题目:给定一个数组,它里面除了一个元素外,其他元素都重复了三次,要求在空间复杂度为O(1),时间复杂度为O(n)的约束下,查找到只重复了一次的元素。

在一个小时内设计出满足条件的算法并编写正确的代码,难度相当大。我们先从简单的角度思考,一种做法是先将数组进行排序,然后从头到尾遍历一次,就可以找到重复一次的元素,但问题在于排序所需要时间为O(n*lg(n)),这就超出了题目对时间的限制,从题目的要求看,不能分配多余空间,并且时间复杂度只能是O(n),这意味着算法必须对数组遍历1次就要找出给定元素。

普通的查找算法在给定条件约束下都无法适用,此时我们必须考虑复杂抽象的位操作。根据题目描述,除了一个元素外,其余元素都重复了三次,我们拿到一个重复3次的元素,将其转换为二进制,如果某个比特位的值是1,那么如果我们遍历一次数组,该位置见到的1一定超过3次以上。看一个具体例子,假设一个重复三次的元素值是2,它的二进制格式为011,那重复三次就是010,010,010,于是下标为0和1的比特位的1就出现了3次,假设我们有一种机制,能够在某个比特位上检测到该位出现的1有三次就清零,那么所有重复三次的元素将会被清除,只剩下重复1次的元素。

我们看个具体例子,例如2,2,2,3,他们对应的二进制位010,010,011,010,把他们累起来有: 010 010 010 =(下标为1的比特位上出现三次1,因此把该位清除为0)=>000 011 011 => 011 => 3 从上面例子看到,我们只要监控每一个比特位,一旦发现在该比特位上出现三次1就把它清0,由于除了一个元素外,其他元素都重复了三次,因此相应的比特位上肯定都相应出现三次1,而只重复1次的元素在相应比特位上的1只出现1次因此不会被清零,由此遍历一次后,只有出现1次的元素的比特位上的1保留下来,这样我们就把出现1次的元素给抽取出来。

问题在于我们如何实现监控每个比特位是否出现三次1的机制。我们设置两个变量towOnes,oneOnes,当某个比特位第一次出现1时,我们把oneOnes对应的位置比特位设置为1,当某个比特位第二次出现为1时,把oneOnes对应的比特位设置为0,在twoOnes对应的比特位设置为1,当对应比特位第三次出现1时,将towOnes对应比特位设置为0,下面的代码可以实现比特位的监控机制:

//E是当前从数组中读入的元素
int T = towOnes;
int O = oneOnes;
twoOnes = T ^ (T & E);  //如果某个比特位上出现三次1的话将其清除
E = E ^ (T & E);  //把出现三次1的比特位上的1清除
twoOnes = twoOnes | (E & O) ; //如果某个比特位上出现两次1,将其设置到twoOnes对应的比特位上
oneOnes = O ^ E ; //将出现1次的比特位设置到oneOnes上

我们用实例将上面步骤走一遍以便获得跟深刻理解,假设当前数组内容为:2,3,2,2,一开始towOnes =0, oneOnes = 0,一开始读入的元素为2,二进制位010,于是执行代码所示的四个步骤: towOnes = 0 ^ (0 & 010) = 0; E = 010 ^ (0 & 0) = 010 twoOnes = 0 | (0 & 0) = 0; oneOnes = 0 ^ 010 = 010 于是,T = 0, O = 010 我们看下标为1的比特位第一次出现1时,oneOnes对应的比特位也设置为1.我们再看输入第二个元素的处理,第二个元素是3,二进制位011,于是有: twoOnes = 0 ^ (0 & 011) = 0 E = 011 ^ (0 & 011) = 011 twoOnes = 0 | (011 & 010) = 010 oneOnes = 010 ^ 011 = 001 于是有T = 010, O = 001 从上面结果看出,下标为1的比特位连续出现两个1,于是twoOnes对应的比特位也设置为1,oneOnes对应比特位设置为0,下标为0的比特位第一次出现1,所以oneOnes对应比特位设置为1. 再次读入第三个元素2,其二进制位010,于是有: twoOnes = 010 ^ (010 & 010) = 0 E = 010 ^ (010 & 010) = 0 twoOnes = 0 | (0 & 001) = 0 oneOnes = 001 ^ 0 = 001 于是有T=0, O=001 从上面运算过程我们看到,再次读入010时,twoOnes在给定下标的位置也是1,也就是下标为1的比特位上此时看到1第三次出现,于是把twoOnes在相应位置上的比特位清0,oneOnes比特位上的数字保持不变。 读入最后一个元素是2,也是010,相应的运算过程有: twoOnes = 0 ^ (0 & 010) = 0 E = 010 ^ (0 & 010) = 010 twoOnes = 0 | (010 & 001) = 0 oneOnes = 001 ^ 010 = 011

此时所有元素处理完毕,oneOnes比特位对应的1恰好就是只重复一次的元素3对应比特位上的1,也就是oneOnes对应的值就是只重复1次元素的值。我们遍历数组所有元素,执行上面算法后就可以得到只重复1次的元素值,由于算法只需遍历一次数组,同时没有分配任何新内存,因此时间复杂度是O(n),空间复杂度是O(1)。我们看看完整实现代码:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;

public class Searching {
    int extractOneTimeElement(int[] threeTimesArray) {
        //分别用于记录只出现1次的比特位和2次的比特位
        int  oneOnes = 0;
        int  twoOnes = 0;

        for (int i = 0; i < threeTimesArray.length; i++) {
            int E = threeTimesArray[i];
            int T = twoOnes; 
            int O = oneOnes;
            twoOnes = T ^ (T & E); //去除那些出现过三次的比特位1
            E = E ^ (T & E); //去除出现过3次的比特位1
            twoOnes = twoOnes | (E & O); //设置出现两次的比特位1
            oneOnes = O ^ E; //设置只出现1次的比特位1
        }

        return oneOnes;
    }

     public static void main(String[] args) {
        int[] A = new int[]{2, 2, 2, 4, 7, 11, 4, 4, 5,5,5, 7,7, 9,9,9};
        Searching s = new Searching();
        int oneTimeElement = s.extractOneTimeElement(A);
        System.out.println("The one time element is : " + oneTimeElement);
     }
}

代码中初始化了一个数组,里面除了11外所有元素都重复出现3次,代码运行后输出的结果正是只从复出现1次的数值11.

原文发布于微信公众号 - Coding迪斯尼(gh_c9f933e7765d)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

Python元编程:控制你想控制的一切

很多人不理解“元编程”是个什么东西,关于它也没有一个十分准确的定义。这篇文章要说的是Python里的元编程,实际上也不一定就真的符合“元编程”的定义。只不过我...

2884
来自专栏Ldpe2G的个人博客

MXNet Scala 学习笔记 二 ---- 创建新的 Operator

(比如Python、Scala)采用现有的操作子来组合,比如实现 Selu 激活函数。

1332
来自专栏aCloudDeveloper

string 之 strchr函数 和 strstr函数(BF算法和KMP算法的应用)

Author: bakari  Date: 2012/8/9 继上篇。。。。。 下面是我写的代码与源码作的一些比较,均已严格测试通过,分别以“string 之”...

2689
来自专栏北京马哥教育

让你的Python代码更加pythonic

何为pythonic? pythonic如果翻译成中文的话就是很python。很+名词结构的用法在中国不少,比如:很娘,很国足,很CCTV等等。 我的理解为...

2084
来自专栏Python小屋

Python+tensorflow计算整数阶乘的方法与局限性

本文代码主要演示tensorflow的基本用法。 import tensorflow as tf # 创建变量,保存计算结果 start = tf.Variab...

3625
来自专栏Seebug漏洞平台

以太坊智能合约OPCODE逆向之理论基础篇

在我们对etherscan等平台上合约进行安全审查时,常常会遇到没有公布Solidity源代码的合约,只能获取到合约的OPCODE,所以一个智能合约的反编译器对...

1963
来自专栏HTML5学堂

为什么不要在 JavaScript 中使用位操作符?

如果你的第一门编程语言不是 JavaScript,而是 C++ 或 Java,那么一开始你大概会看不惯 JavaScript 的数字类型。在 JavaScrip...

36010
来自专栏知识分享

指针--解决的疑惑

简单的就不说了,今天学链表,在链表中遇到了自己疑惑的事情,后来在网上查二级指针,搜出来一个,才解除了自己的疑惑 下面是对原文的复制,,最后有自己的链表程序--原...

3107
来自专栏take time, save time

你所能用到的数据结构(七)

十、装配火车的乐趣       国庆放假结束了,第一天真是不想来上班啊,接着国庆之前的吧,上一篇写的是利用数组实现堆栈的结构,使用数组的两个致命的弱点是大小必须...

3478
来自专栏python3

习题27:if和else

if语句为代码创建了一个所谓的"分支",就跟RPG游戏中的情节分支一样,if语句告诉你的脚本:“如果这个布尔表达式为真,就运行接下来的代码,否则就跳过这一段”

561

扫码关注云+社区

领取腾讯云代金券