Leetcode SingleNumber I & II & III 136/137/260

SingleNumber I:

题目链接：https://leetcode-cn.com/problems/single-number/

题意：

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

　　说明：

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

　　示例 1:

　　输入: [2,2,1]

　　输出: 1

　　示例 2:

　　输入: [4,1,2,1,2]

　　输出: 4

分析：

　　利用异或（xor）运算，两个相同的数异或为0

代码如下：

 class Solution {

 public:

     int singleNumber(int A[], int n) {

         int ans = ;

         for(int i = ; i < n; ++i) {

             ans ^= A[i];

         }

         return ans;

     }

 };

SingleNumber II:

题目链接：https://leetcode-cn.com/problems/single-number-ii/

借鉴：https://www.cnblogs.com/grandyang/p/4263927.html

题意：

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

说明：

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

示例 1:

　　输入: [2,2,3,2]

　　输出: 3

示例 2:

　　输入: [0,1,0,1,0,1,99]

　　输出: 99

分析1：

　　与第一题的不同是这里相同的数出现了3次，如果能定义一种3进制异或运算，就可以以第一题的方式解出这道题了。

代码如下：

 class Solution {

 public:

     int singleNumber(vector<int>& nums) {

         int res = ;

         for (int i = ; i < ; ++i) {

             int sum = ;

             for (int j = ; j < nums.size(); ++j) {

                 // 取nums[j]的第i位值，然后加起来

                 sum += (nums[j] >> i) & ;

             }

             // sum目前的有进位相加的结果，模3以后就是无进位相加的结果

             res |= (sum % ) << i;

         }

         return res;

     }

 };

分析2：

　　还有一种解法，思路很相似，用3个整数来表示INT的各位的出现次数情况，one表示出现了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。

ones 代表第i^th 位只出现一次的掩码变量
twos 代表第i^th 位只出现两次次的掩码变量
threes 代表第i^th 位只出现三次的掩码变量

代码如下：

 class Solution {

 public:

     int singleNumber(vector<int>& nums) {

         int one = , two = , three = ;

         for (int i = ; i < nums.size(); ++i) {

             // one & nums[i]的结果某一位上为1意味着这一位在上一轮出现过一次，在这一轮又出现过一次，那么也就意味着出现了两次

             // two此时包含所有出现过2次和3次的

             two |= one & nums[i];

             // one的某一位为1，表示之前出现过1次。如果nums[i]对应位为0，one的某一位没有变化；如果nums[i]对应位为1，one的某一位变为0，表示这一位出现2次了。

             // one的某一位为0，表示之前出现过0次或2次。如果nums[i]对应位为0，one的某一位没有变化；如果nums[i]对应位为1，one的某一位变为1，表示这一位出现过1次或3次。

             // one此时包含所有出现过1次和3次的

             one ^= nums[i];

             three = one & two;

             // 消掉3次的

             one &= ~three;

             two &= ~three;

         }

         return one;

     }

 };

分析3：

　　和分析2一样，不过这次只需要2个变量。

ones 代表第i^th 位只出现一次的掩码变量
twos 代表第i^th 位只出现两次次的掩码变量

ones[i]原：ones第i位二进制位原来的值

twos[i]原：twos第i位二进制位原来的值

x[i]：所要异或的数的第i位二进制位的值

ones[i]：ones第i位二进制位异或后的值

ones[i]原	twos[i]原	x[i]	ones[i]	twos[i]
0	0	0	0	0
0	1	0	0	1
1	0	0	1	0
1	1	0	x	x
0	0	1	1	0
0	1	1	0	0
1	0	1	0	1
1	1	1	x	x

ones的韦恩图
x\ones原twos原	00	01	10	11
0	0	0	1	x
1	1	0	0	x

twos的韦恩图
x\onestwos原	00	01	10	11
0	0	1	0	x
1	1	0	0	x

得到公式为：

ones = (ones ^ x) & ~twos;
twos = (twos ^ x) & ~ones;

代码如下：

 class Solution {

 public:

     int singleNumber(vector<int>& nums) {

         int twos = , ones = ;

         for (int i = ; i < nums.size(); ++i) {

             // ones ^ nums[i]后ones的某一位1可能表示原来出现过0次，也可能表示原来出现过2次

             // & ~twos表示把原来出现过2次的部分删掉

             ones = (ones ^ nums[i]) & ~twos;

             // twos ^ nums[i]后twos的某一位1可能表示目前出现过2次，也可能表示目前出现过1次

             // & ~ones表示把目前出现过1次的部分删掉

             twos = (twos ^ nums[i]) & ~ones;

         }

         return ones | twos;

     }

 };

SingleNumber III:

题目链接：https://leetcode-cn.com/problems/single-number-iii/

题意：

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

示例 :

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

输出: [3,5]

注意：

1. 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

分析：

　　将所有数异或一遍，那个异或完后一定有某一位是1，这意味着两个数在这一位上不同，因此只要把这一位上为0的数和为1的数分别全部异或一遍就能得到只出现一次的2个元素了。

代码如下：

 class Solution {

 public:

     vector<int> singleNumber(vector<int>& nums) {

         vector<int> ans;

         int a = , b = , lowbit = ;

         for(int i = ; i < (int)nums.size(); ++i) {

             lowbit ^= nums[i];

         }

         lowbit = lowbit & (-lowbit);

         for(int i = ; i < (int)nums.size(); ++i) {

             if(nums[i] & lowbit) a ^= nums[i];

             else b ^= nums[i];

         }

         ans.push_back(a);

         ans.push_back(b);

         return ans;

     }

 };

巴特西

Leetcode SingleNumber I & II & III 136/137/260

SingleNumber I:

题意：

分析：

代码如下：

SingleNumber II:

题意：

分析1：

代码如下：

分析2：

代码如下：

分析3：

代码如下：

SingleNumber III:

题意：

分析：

代码如下：

最新文章

热门文章