LeetCode-136、137、260. 只出现一次的数字I、II、 III

    xiaoxiao2022-07-03  129

    目录

    136. 只出现一次的数字

    137. 只出现一次的数字 II

    260. 只出现一次的数字 III


    136. 只出现一次的数字

    【题目】:

    【代码】:

     


    137. 只出现一次的数字 II

    【题目】:

    【代码】:

    方法1:

    java中存储一个int型整数,需要32位,我们也开32位的数组。以下为了表示方便只用4位。

    假设有数组[5,1,5,1,5,1,4],写成二进制为:

    5:0110

    1:0001

    5:0110

    1:0001

    5:0110

    1:0001

    4:0100

    T:0433       //每一列的和

    R:0100       //模3

    (T表示total,合计,每一列的和。R表示对3取模完之后的结果)

    对T中的数值每一位取模3可以得到,出现了3的整数倍次的,取模完结果都是0;出现了非3的整数倍次的,即只出现了一次的那个数,取模完结果都为1,说明只出现一次的那个数,在当前这个位有出现过,最后也可以求出这个值。

    但是时间复杂度好像不是线性时间复杂度~~~~~

    效果:

    方法2:我们想设计一个方法,使得一个数出现3次时能自动抵消为0,相当于模3,即

    参考1:https://blog.csdn.net/pengchengliu/article/details/90437071

    参考2:http://www.cnblogs.com/king-3/p/8763000.html

    效果:

     


    260. 只出现一次的数字 III

    【题目】:

    【代码】:

    两个不相等的元素在位级表示上必定会有一位存在不同。

    将数组的所有元素异或得到的结果ret为不存在重复的两个元素异或的结果。即例中的 5^3=6,(101^011=110)

    bit=ret &( -ret)得到出 bit 最右侧第一个不为 0 的位,也就是只出现一次的两个元素在位级表示上最右侧不同的那一位,利用这一位就可以将所有元素分为两组,一组该位为1,另一组该位为0,对两个数组中的元素分别相与得到这两个不相同的数字。

    【效果】:

     

    最新回复(0)