LeetCode-只出现一次的数字I II III

Posted on | In

陆续做完了关于^&|的题目，在此想总结下。

只出现一次的数字I

只出现一次的数字I

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗

示例 1:

1
2
3
> 输入: [2,2,1]
> 输出: 1
>

示例 2:

1
2
3
> 输入: [4,1,2,1,2]
> 输出: 4
>

^运算有很多性质在这里我们需要知道的是：

  1. 零与任何数^为任何数
  2. 任何数与其自身^为零，并且具有交换律。

[1, 2, 2, 3, 3] ==> 1^2^2^3^3 = 1

^的交换律体现在 [2, 1, 2, 3, 3] ==> 2^1^2^3^3 = 1

从上述例子可知，如果一个序列中某些数字出现两次可以通过^将其消去，最后的结果为该数列中出现一次的数字。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < nums.size(); ++i)
            ans ^= nums[i];
        return ans;
    }
};

只出现一次的数字 II

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

1
2
3
> 输入: [2,2,3,2]
> 输出: 3
>

示例 2:

1
2
3
> 输入: [0,1,0,1,0,1,99]
> 输出: 99
>

第一题我们谈到了^的神奇之处，但这里是三个同样的数字，这样第一题的方法就失效了。

由于整数在计算机内表示很简单，由一系列01的组合构成，我们可以开辟一个32位的数组，存储int的每一位01。 由于有三个相同的数字，当某一位上的1之和为3，将其置为0。重复上面的过程，最后的数组里存储就是唯一出现一次的元素的32位01的组合，最后将其转换成十进制。

下面代码有两个位置需要注意下

  1. 第8行，将十进制转换成二进制，其实也就是辗转相除法，向左移一位相当于除以二。
  2. 第16行，想将1移到对应的位上，然后做|运算，就可以将该数字转换成十进制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int singleNumber(vector<int>& nums) {
       vector<int> cur(32);
       for(int i = 0; i < nums.size(); ++i){
           for(int j = 0; j < cur.size(); ++j){
               //leetcode 对负数左移有限制,故要转换成无符号整型
               cur[j] += ((unsigned int) nums[i] >> j) % 2;   
               if(cur[j] == 3)
                    cur[j] = 0;
           }
       }
       int ans = 0;
       for(int i = 0; i < cur.size(); ++i){
           if(cur[i])
            ans |= 1 << i;
       }
       return ans;
    }
};

只出现一次的数字 III

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例 :

1
2
3
> 输入: [1,2,1,3,2,5]
> 输出: [3,5]
>

根据第一题给出的结论，将序列中所有的数字都^则剩下的就是两个唯一出现一次元素的^的结果。如[1,2,1,3,2,5]全部^一次结果是 3^5。将序列分为两组，分组是根据3和5低位的1来分的，从低位开始如果011（3）和101（5），我们选取第二位来作为划分该序列的标准，第二位为1的和3一组，第二位不为1的和5一组。最后再利用第一题的结论，做一次^运算就可以把两个只出现一次的元素找出来了。

3^5 = (0100)2 第三位可以作为区分两组不同数字的依据，但不是所有的数字都像3和5这么短小，故要使用低位运算将其截取到最低位的1和后面所有的0。

低位运算

lowbit(w)定义为非整数n在二进制表示下“最低位的1及其后面的所有0”构成的数值

如: n = 10，二进制表示为（1010)2， 则其低位lowbit(10) = (10)2 = 2.

公式有: lowbit(n) = n & (~n + 1) = n & ( - n )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int cur = 0;
        vector<int> ans{0, 0};
        for(int i = 0; i < nums.size(); ++i)
            cur ^= nums[i];
        cur &= (~cur + 1);
        for(int i = 0; i < nums.size(); ++i){
            if((cur & nums[i]) == cur)
                ans[0] ^= nums[i];
            else
                ans[1] ^= nums[i];
        }
        return ans;
    }
};