LeetCode－136. Single Number/137. Single Number II/260. Single Number III

待我称王封你为后i 2022-07-26 04:12 182阅读 0赞

## 136. Single Numbe ##

Problem：

> 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?

Analysis：

> 由于要求时间复杂度：O（n），没有其余空间，所以往位运算方面考虑，即：用异或运算与每一个值，因为两个相同的异或后为零，所有数和当0异或值不变，而且异或运算支持交换律和结合律。

Answer：

public class Solution {
        public int singleNumber(int[] nums) {
            for(int i=1;i<nums.length;i++){
                nums[0] ^= nums[i];
            }
            return nums[0];
        }
    }

--------------------

## 137. Single Number II ##

Problem:

> 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?

Analysis:  
**解法1：**

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

**解法2：**

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

Answer:  
解法1：

public class Solution {
        public int singleNumber(int[] nums) {
            int result=0;
            int[] count= new int[32];
            for(int i=0;i<32;i++){
                for(int j=0;j<nums.length;j++){
                    if(((nums[j]>>i) & 1)>0) count[i]++;
                }
                result |= (count[i] % 3) << i;
            }
            return result;
        }
    }

**解法1改进，**

> 其实看得明白的可以知道上个解法count数组每一个都是纪录一位，每一位不互相利用，也就是可以用完之后给其他的位用，所以没有必要开一个数组，只是一位用完置零即可。

public class Solution {
        public int singleNumber(int[] nums) {
            int result=0,count=0;
            for(int i=0;i<32;i++){
                for(int j=0;j<nums.length;j++){
                    if(((nums[j]>>i) & 1)>0) count++;
                }
                result |= (count % 3) << i;
                count = 0;
            }
            return result;
        }
    }

位运算解决方法：  
解法2：

public class Solution {
        public int singleNumber(int[] nums) {
           int one=0,two=0,three=0;
           for(int i=0;i<nums.length;i++){
               two |= one & nums[i];
               one ^=nums[i];
               three = one & two;
               one &= ~three;
               two &= ~three;//
           }
           return one;
        }
    }

**解释：**

1.  每次循环先计算 twos，即出现两次的 1 的分布，然后计算出现一次的 1 的分布，接着 二者进行与操作得到出现三次的 1的分布情况
2.  然后对 threes 取反，再与 ones、twos进行与操作，这样的目的是将出现了三次的位置清零。
3.  `one ^=nums[i];`可以使1出现次数大于等于2的次数时自动将这些位清零，也就是总保持最多一次1的分布情况。

--------------------

## 260. Single Number III ##

Problem:

> 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?

Analysis:

> **题目大意**： 给定一个整数数组，其中除两个数字只出现一次外，其余数字均出现两次。找出这两个只出现一次的数字。  
> 例如： 给定 nums =\[1, 2, 1, 3, 2, 5\]，返回 \[3, 5\]  
> 注意： 结果的顺序不重要。因此在上例中，\[5, 3\]也是正确的。
> 
> 你的算法应该满足线性时间复杂度。你可以只使用常数空间复杂度完成题目吗？

**解题思路**：利用位运算，异或

1.  异或数组每一位。 因为相同值异或为0，而且疑惑满足结合律，交换律，所以异或数组每一位结果为个数为1的两个数的异或
2.  `A_XOR_B & (~(A_XOR_B-1))`。 这个代码很有意思，以前知道x&(x-1)是去除最后一位1，而这个是得到最后一个1的位置。其实想利用这个1来区分不同的A和B。因为异或不同为1，既然能够为1，则说明这一位肯定不相同，可以利用这一位做区分。
3.  区分的时候还是利用异或。 如果和last\_bit相同则和A（为了方便返回用res\[0\]代表）异或，如果和last\_bit不相同则和B（为了方便返回用res\[1\]代表）异或。

Answer:

public class Solution {
        public int[] singleNumber(int[] nums) {
            int A_XOR_B = 0;
            for(int i=0;i<nums.length;i++){
                A_XOR_B ^=nums[i];
            }
            int last_bit = A_XOR_B & (~(A_XOR_B-1));
            int[] res={
       0,0};
            for(int i=0;i<nums.length;i++){
                if((last_bit & nums[i]) ==0){
                    res[0] ^=nums[i];
                }
                else{
                    res[1] ^=nums[i];
                }
            }
            return res;
        }
    }