题目:一个Int型数组,存放的数据中有两个重复的次数是奇数次,其他的重复的次数全是偶数次。
要求:找出这两个数据,时间复杂度是O(n) 空间复杂度是O(1)
名词简单解释:
时间复杂度是O(n)案例:遍历一个长度为n的数组,时间复杂度是O(n) 如果在for循环里嵌套一个长度为n的循环那么时间复杂度是O(n2).如果两个for循环有先后顺序,无嵌套关系,时间复杂度还是O(n).
空间复杂度是O(n)案例:创建一个长度为n的数组占用的空间是与n成正比的,空间复杂度是O(n).
解决办法:
(1)假设数据是:55,44,33,44,44,44,22,33,55,55,22,22。
(2)第一步:将数据依次进行异或运算,即:55与44异或运算得到a,a再与33异或运算得到b,一直到最后得到一个数值为x.
步骤详解:
1>“异或”规则:相同为0 不同为1 例如1001异或1010等于0011
2> 进行异或运算以后,所有的出现偶数次的数,变成了0,相当于被剔除,出现奇数次的55中有2个55异或得到0,3个22中有2个异或得到0,最后相当于55和22进行异或运算,得到x(可以肯定的是x不为0)
(3)第二步:假设x的右边的第一位为1(其他位上为1同样可以使用该位),写一个方法假设是public boolean isOne(int value,int num){},用途是判断输入的value在第num位是否为1,返回Boolean结果。将x与原始数据再次进行异或运算。不过要加上isOne方法进行判断,结果是x分别与在第一位上是1的数据异或得到a,第一位上是0的数据异或得到b,a和b就是要求的两个数。
步骤详解:
isOne()方法将数据分为两种即第一位上为0的和第一位上是1的,可以肯定的是要求 的数据a和b一定是不同的两种类型。那么就像是第一步中一样所有的出现偶数次的全部消去,结果是x与22异或得到结果是55,x与55异或得到结果是22。
一些想法:
变形1:一个Int型数组,存放的数据中有两个重复的次数是偶数次,其他的重复的次数全是奇数次。(奇数和偶数变换顺序)
变形2:一个Int型数组,存放的数据中有3个重复的次数是奇数次,其他的重复的次数全是偶数次。(2个变为3个)
变形1:仔细分析的话结果是行不通的,对于第一个的想法可以变成不是异或运算而是同或运算,但是第一步就将要求的两个数a和b剔除了。所以第一步就做不到得到一个上一种的一个肯定不为0的x。就别提第二步了。
变形2:第一步可以实行,得到一个a,b和c 三个数异或。但是不能确定这个结果肯定为0或不为0,事情变得不好处理。可以分类讨论。(此处不做分析)
再看本题该方法的妙处:
依据:
第一步利用数据a和b的相同之处是两者出现的次数是偶数,此条件可以将所有的数据分为两派,此时a和b属于同一方。
第二步利用数据a和b的不同之处是两者至少存在一位不同,此条件可以将所有的数据分为两派,此时a和b属于不同方。
关键方法:巧用异或,解决了关于奇次和偶次的问题。
不论是奇还是偶,还是“两”个数。其实都是表示了0和1世界中的两种可能,代表的是中逻辑,无关数量。知己知彼才能各个突破。
分享到:
相关推荐
它不是那些老套陈旧的动机心理学扯谈。 我并不是说那些传统的应对拖延症的方法理论不对,只是对我无效。当正经历极度消沉的时候,我通常听到的理论的最后一句话是”You just DO IT!”。我有很多的事情要去做。但我...
是做过的,就不会扯谈!开关电源的难点是选变压器与过辐射.现在产品都在朝小型化低成本发展,可以说原来EE,PQ,EPC的变压器都很难装入成品中,必须选用小型高磁通与高频的驱动芯片,高频芯片带来的最直接弊病就是辐射难...
原型模式i的定义:每个函数都有一个prototype(原型)属性,这个属性是一个对象,它的用途是包含可以由特定类型的所有实例共享的属性和方法。比如在构造函数模型中sayInformation()方法,如果声明两个实例就要构造两次...
手把手教你用vue+node+mongodb搭建一个小商城 前期准备工作 v-router的讲解 交流扯谈
编译原理.zip。学习基础知识。CSDN管理员要求20个字描述,没办法,扯谈吧。其实,学校课件这东西只适合上课与自己复习、结构记忆,真正要学东西,还是得看书。
SQL登录时如果采用windows集成身份验证,登录框将会以“机器名\当前... ... 网上看到有人说可以采用OSQL–S instancename –E(在命令行窗口中输入)登录进去后再去修改sa的密码,一番尝试后发现是扯谈,因为采用这种方式