leetcode:single-number-ii（Java位运算）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目

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?

给定一个整型数组，每个数都出现了三次（只有一个数只出现了一次），找到那个只出现一次的数字。要求：时间复杂度O(n)，空间复杂度O(1)。这类问题通常使用位运算解决。

解法1：int数据共有32位，可以用32变量存储：这N个元素中各个二进制位上“1” 出现的次数。最后再进行“模3”操作，如果为1，那说明这一位是要找的数字二进制表示中为1 的那一位

C实现：

class Solution {
public:
int singleNumber(int A[], int n) {
int bitnum[32]={0}; //使用bitnum数组保存int数组n个元素
int res=0;
for(int i=0; i<32; i++){
for(int j=0; j<n; j++){
bitnum[i]+=(A[j]>>i)&1;
//数组中每个元素都对1取与运算，并将运算结果叠加在bitnum数组第i位
}
res|=(bitnum[i]%3)<<i; //将叠加的结果模3 操作，确定bitnum[i]
}
return res; //循环完，得到bitnum数组每一个元素，bitnum数组就是那个只出现一次的元素
}
};

JAVA实现：

public class Solution {
public int singleNumber(int[] A) {
int result = 0;
int count = 0;
for(int i = 0; i <= 31; i++){ //循环int类型的每一个bit位
count = 0;
for(int j = 0; j <= A.length - 1; j++){//计算所有数的第i bit位为1的个数
count += (A[j] >> i) & 1;
}
result |= (count % 3) << i;//结果执行与与运算
}
return result;
}
}

解法2：这是一个更快一些的解法，利用三个变量分别保存各个二进制位上 1 出现一次、两次、三次的分布情况，最后只需返回变量一就行了。

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

解释：每次循环先计算 twos，即出现两次的 1 的分布，然后计算出现一次的 1 的分布，接着二者进行与操作得到出现三次的 1 的分布情况，然后对 threes 取反，再与 ones、twos进行与操作，这样的目的是将出现了三次的位置清零。这个方法虽然更快、更省空间了，但是并不通用。

类似题

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

Note:

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

class Solution {
public:
int singleNumber(int A[], int n) {
int res=0;
for(int i=0;i<n;i++){
res=res^A[i];
}
return res;
}
};

Java的位运算

Java中定义了位运算符，应用于整数类型(int)，长整型(long)，短整型(short)，字符型(char)，和字节型(byte)等类型。位运算符作用在所有的位上，并且按位运算。位运算符的计算都是在二进制格式下进行的，也就是说如果给出的数格式不是二进制格式需要先转成二进制格式。

常用的位运算符

1．与运算符

与运算符用符号“&”表示，其使用规律如下：两个操作数中位都为1，结果才为1，否则结果为0，例如下面的程序段。

public class data13
{
public static void main(String[] args)
{
int a=129;
int b=128;
System.out.println("a 和b 与的结果是："+(a&b));
}
}
运行结果
a 和b 与的结果是：128
下面分析这个程序：
“a”的值是129，转换成二进制就是10000001，而“b”的值是128，转换成二进制就是10000000。根据与运算符的运算规律，只有两个位都是1，结果才是1，可以知道结果就是10000000，即128。

2．或运算符

或运算符用符号“|”表示，其运算规律如下：两个位只要有一个为1，那么结果就是1，否则就为0，下面看一个简单的例子。

public class data14
{
public static void main(String[] args)
{
int a=129;
int b=128;
System.out.println("a 和b 或的结果是："+(a|b));
}
}
运行结果
a 和b 或的结果是：129
下面分析这个程序段：
a 的值是129，转换成二进制就是10000001，而b 的值是128，转换成二进制就是10000000，根据或运算符的运算规律，只有两个位有一个是1，结果才是1，可以知道结果就是10000001，即129。

3．非运算符
非运算符用符号“~”表示，其运算规律如下：如果位为0，结果是1，如果位为1，结果是0，下面看一个简单例子。

public class data15
{
public static void main(String[] args)
{
int a=2;
System.out.println("a 非的结果是："+(~a));
}
}

4．异或运算符

异或运算符是用符号“^”表示的，其运算规律是：两个操作数的位中，相同则结果为0，不同则结果为1。下面看一个简单的例子。

public class data16
{
public static void main(String[] args)
{
int a=15;
int b=2;
System.out.println("a 与 b 异或的结果是："+(a^b));
}
}
运行结果
a 与 b 异或的结果是：13
分析上面的程序段：a 的值是15，转换成二进制为1111，而b 的值是2，转换成二进制为0010，根据异或的运算规律，可以得出其结果为1101 即13。