LeetCode SingleNumber I,II,III
原创
LeetCode SingleNumber I,II,III
原创
136. Single Number
Given a non-empty 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?
Example 1:
Input: [2,2,1]
Output: 1Example 2:
Input: [4,1,2,1,2]
Output: 4题目大意：一个数组中只有一个数字只出现一次，其他的都出现两次，求这个只出现一次的数字
class Solution {
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int x = 0;
for (int i = 0; i < nums.length ;i++){
x = x^nums[i];
}
return x;
}
}由于，异或运算支持交换律和结合律，所以，只要是出现次数为偶数次的数字，采用异或运算，结果为0；如此一来，如果数组中的一个数字只出现一次，那么最后的异或运算的结果就是这个数字。
137. Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,3,2]
Output: 3Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99题目大意：只有一个数字是出现一次，其他的数字都是出现三次。
class Solution {
public int singleNumber(int[] nums) {
int a = 0;
int b = 0;
for (int n : nums) {
a = (a^n) & (~b);
b = (b^n) & (~a);
}
return a;
}
}数组为[2,2,2,3]，一共有四个元素，进行四次循环。
第一次循环，b=(0000^0010)&1111=0010=2，a=(0000^0010)&1101=0000=0
第二次循环，b=(0010^0010)&1111=0000=0，a=(0000^0010)&1111=0010=2
第三次循环，b=(0000^0010)&1101=0000=0，a=(0010^0010)&1111=0000=0
第四次循环，b=(0000^0011)&1111=0011=3，a=(0000^0011)&1100=0000=0
如果是出现两次的话，用一个bit就可以
比如 b，初始为0
当5第1次出现时， b=5
当5第2次出现是， b清空为0，表示b可以去处理其他数字了
所以，最后 如果 b !=0的话，b记录的就是只出现了一次的那个数字
->公式就是 b = b xor i 或者 b = b^i
那么，如果是三次的话，香浓定理，需要用2bits进行记录
当5第一次出现的时候，b = 5, a=0, b记录这个数字
当5第二次出现的时候，b = 0, a=5， a记录了这个数字
当5第三次出现的时候，b = 0, a=0， 都清空了，可以去处理其他数字了
所以，如果有某个数字出现了1次，就存在b中，出现了两次，就存在a中，所以返回 a|b
公式方面 ，上面两次的时候，b清空的公式是 b = b xor i
而第三次时，b要等于零，而这时a是True，所以再 & 一个a的非就可以，b = b xor & ~a
-> b = b xor i & ~ a
a = a xor i & ~b260. Single Number 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.
Example:
Input: [1,2,1,3,2,5]
Output: [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?
public int[] singleNumber(int[] nums) {
int x = 0;
for ( int num :nums){
x = x ^num;
}
int [] res = new int[2];
int n = x & -x;
for (int i = 0 ; i <nums.length;i++){
if ((n & nums[i]) !=0){
res[0] ^= nums[i];
}else {
res[1] ^= nums[i];
}
}
return res;
}- 先将所有的数字进行异或运算，那么得到的结果就是这两个数字的异或运算结果，并且结果不为0
- 找到上述结果中的某个为1的位，那么，根据整个数组中这一位是1还是0，分为两个数组，第一个数组：这一位为0的数（包括重复的数和单独的一个数），第二个数组：这一位为1的数（包括重复的数和另一个单独的一个数）
- 对这两组数分别全部异或运算处理，那么得到的两个结果就是这两个单独的数
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
