Given an array of integers, every element appears three times except for one. Find that single one.
Could you implement it without using extra memory?
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
A:
-------4th pass -------idea borrowed from EPI------------
用 zeros, ones, twos 3个变量代表每个bit上的积累的1的count%3 是多少。(每个bit,有且只有一个为1)
然后,每次计算的时候,该bit要得到 1,有2种情况。
1: 下一位是1,且新来的A[i]为1 (进位的结果)
2 : 本来是1, 且新来的A[i] 为0 , (承袭之前的结果,没有变化)
public class Solution { public int singleNumber(int[] A) { int zeros = -1, ones = 0, twos = 0; // result is the ones, -1 is OB1111.1111 for(int i =0;i<A.length;i++){ int old0 = zeros, old1 = ones, old2 = twos; zeros =(old2 & A[i]) | (old0 & ~A[i]); ones = (old0 & A[i]) | (old1 & ~A[i]); twos = (old1 & A[i]) | (old2 & ~A[i]); } return ones; } }
-------3th pass -------idea borrowed from EPI------------
用one,two两个int变量,代表,每一个bit,我们发现的1的次数。
这里,为了不额外声明空间,我们用了A[0],A[1]两个位置。
这里,比较tricky的地方就是 我们在计算初始的A[0],A[1]的时候,需要先计算A[0],再利用新的A[0]和旧的A[1]来计算A[1]。
然后在循环里,我们先计算A[1],再利用这个新的A[1]来 计算A[0]
public class Solution { public int singleNumber(int[] A) { if(A.length==1) return A[0]; // A[0] is the the time that 1 occurs in odd number, A[1] is the even number, A[0] ^= A[1]; // this is the lower bit A[1] &= ~A[0]; // high bit, but calculated use the new A[0] for(int i = 2;i<A.length;i++){ A[1] = ~A[1] & (A[0] &A[i]) | A[1] & ~(A[0]&A[i]); // for bits 2, A[0] = (A[0]| A[i]) & ~(A[0]&A[i]&A[1]); // for bits 1 } return A[0] & ~(A[0]&A[1]); } }
仔细体会吧, Tiger, 貌似EPI上有更简单的算法,哦,这里, A[1] 代表高位,A[0]代表低位。 注意处理11的情况,这时候,我们要把他们当作00来对待。
-----------------第二遍,-----------都是数每一个位置,1的个数--
网上的一个做法是: 对于除出现一次之外的所有的整数,其二进制表示中每一位1出现的次数是3的整数倍,将所有这些1清零,剩下的就是最终的数。 用ones记录到当前计算的变量为止,二进制1出现“1次”(mod 3 之后的 1)的数位。用twos记录到当前计算的变量为止,二进制1出现“2次”(mod 3 之后的 2)的数位。当ones和twos中的某一位同时为1时表示二进制1出现3次,此时需要清零。即用二进制模拟三进制计算。最终ones记录的是最终结果。 时间复杂度:O(n)
public class Solution { public int singleNumber(int[] A) { int n = A.length; // use 32 bit to count int result =0; for(int i =0;i<32;i++){ int bit =0; for(int j =0;j<n;j++) bit = ((A[j]>>i&1)+bit)%3; result += bit<<i; } return result; } }错误:
1: if( a & b != 0 ) // given a and b are integer
这样是不对的,因为涉及到 & != 的优先级关系, 会先计算 b!=0.
导致 if (int & boolean )
2: bit运算中, 没有 || && 这些, 那些只是逻辑运算。
1: 全1 的int类型是 int res = Integer.MIN_VALUE-1 (其实直接就是-1);
而真正的Integer.MIN_VALUE 是 1000......0000(31个0)。
既然,不让用extra space,但是又不能不用一点儿space, 就只好在数组里更改数值了。
扩展一:
给定一个包含n个整数的数组,除了一个数出现二次外所有的整数均出现三次,找出这个只出现二次的整数。ones记录1出现一次的数,twos记录1出现2次的数,容易知道twos记录的即是最终结果。
扩展二:
给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。使用二 进制模拟a进制,累计二进制位1出现的次数,当次数达到a时,对其清零,这样可以得到b mod a次x,c mod a次y的累加。遍历剩余结果(用ones、twos、fours...变量表示)中每一位二进制位1出现的次数,如果次数为b mod a 或者 c mod a,可以说明x和y的当前二进制位不同(一个为0,另一个为1),据此二进制位将原数组分成两组, 一组该二进制位为1,另一组该二进制位为0。这样问题变成“除了一个整数出现a1次(a1 = b 或 a1 = c)外所有的整数均出现a次”,使用和上面相同的方式计算就可以得到最终结果,假设模拟a进制计算过程中使用的变量为ones、twos、 fours...那么最终结果可以用ones | twos | fours ...表示。
No comments:
Post a Comment