Leetccode 136 SingleNumber I
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?
1.自己想到了先排序,再遍历数组找,复杂度较高
2.参考其他想法,最好的是利用异或,详见代码
import java.util.Arrays; public class S136 { public int singleNumber(int[] nums) {
//AC but not good
/* Arrays.sort(nums);
int i = 0;
for(;i<nums.length-1;i+=2){
if(nums[i]!=nums[i+1]){
return nums[i];
}
}
return nums[i];*/
//best one 异或运算的神奇之处 1.a^b == b^a 2.0^a == a
if(nums.length<1)
return 0;
int ret = nums[0];
for(int i = 0;i<nums.length;i++){
ret = ret^nums[i];
}
return ret;
}
}
Leetccode 137 SingleNumber II
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?
1.利用排序和遍历同样可以AC
2.利用异或,详见代码
public class S137 {
public int singleNumber(int[] nums) {
//AC but not good
/* Arrays.sort(nums);
int i = 0;
for(;i<nums.length-1;i+=3){
if(nums[i]!=nums[i+1]){
return nums[i];
}
}
return nums[i];*/
//a general algorithm
int a[] = new int[32];
int ret = 0;
for(int i = 0;i<32;i++){
for(int j = 0;j<nums.length;j++){
a[i] += (nums[j]>>i)&1; }
ret |= (a[i]%3)<<i;
}
return ret;
}
}
Leetccode 260 SingleNumber III
Given an array of numbers nums
, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
For example:
Given nums = [1, 2, 1, 3, 2, 5]
, return [3, 5]
.
Note:
- The order of the result is not important. So in the above example,
[5, 3]
is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
思路:先将所有元素异或得到的结果ret肯定不为零,再移位寻找第一个不为零的二进制位,记录位置pos。再遍历数组,将所有pos位置为零的数异或得到num1,所有pos位置为一的数异或得到num2,num1和num2即answer。因为ret中不为零的二进制位所对应位肯定是num1和num2对应位异或,必定是num1和num2此位不同,将数组分为两组分别异或其实就是第一种情况的解法了。详见代码
public class S260 {
public int[] singleNumber(int[] nums) {
int num1= 0,num2 = 0;
int ret = 0;
for(int i = 0;i<nums.length;i++){
ret ^= nums[i];
}
int pos = 0;
for(;pos<32;pos++){
if((ret>>pos&1) == 1){
break;
}
}
for(int i = 0;i<nums.length;i++){
if((nums[i]>>pos&1)==1){
num1 ^= nums[i];
}else{
num2 ^= nums[i];
}
}
int rets[] = {num1,num2};
return rets;
}
}