C++实现LeetCode(137.单独的数字之二)
[LeetCode] 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]Example 2:
Output: 3
Input: [0,1,0,1,0,1,99]这道题是之前那道 Single Number 的延伸,那道题的解法就比较独特,是利用计算机按位储存数字的特性来做的,这道题就是除了一个单独的数字之外,数组中其他的数字都出现了三次,还是要利用位操作 Bit Manipulation 来解。可以建立一个 32 位的数字,来统计每一位上1出现的个数,如果某一位上为1的话,那么如果该整数出现了三次,对3取余为0,这样把每个数的对应位都加起来对3取余,最终剩下来的那个数就是单独的数字。代码如下:
Output: 99
解法一:
class Solution {public:int singleNumber(vector& nums) {int res = 0; for (int i = 0; i < 32; ++i) {int sum = 0; for (int j = 0; j < nums.size(); ++j) {sum += (nums[j] >> i) & 1; }res |= (sum % 3) << i; }return res; }};
还有一种解法,思路很相似,用3个整数来表示 INT 的各位的出现次数情况,one 表示出现了1次,two 表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。
- ones代表第 ith 位只出现一次的掩码变量
- twos代表第 ith 位只出现两次次的掩码变量
- threes代表第 ith 位只出现三次的掩码变量
解法二:
class Solution {public:int singleNumber(vector& nums) {int one = 0, two = 0, three = 0; for (int i = 0; i < nums.size(); ++i) {two |= one & nums[i]; one ^= nums[i]; three = one & two; one &= ~three; two &= ~three; }return one; }};
下面这种解法思路也十分巧妙,根据上面解法的思路,我们把数组中数字的每一位累加起来对3取余,剩下的结果就是那个单独数组该位上的数字,由于累加的过程都要对3取余,那么每一位上累加的过程就是 0->1->2->0,换成二进制的表示为 00->01->10->00,可以写出对应关系:
00 (+) 1 = 01
01 (+) 1 = 10
10 (+) 1 = 00 ( mod 3)
用 ab 来表示开始的状态,对于加1操作后,得到的新状态的 ab 的算法如下:
b = b xor r & ~a;
a = a xor r & ~b;
这里的 ab 就是上面的三种状态 00,01,10 的十位和各位,刚开始的时候,a和b都是0,当此时遇到数字1的时候,b更新为1,a更新为0,就是 01 的状态;再次遇到1的时候,b更新为0,a更新为1,就是 10 的状态;再次遇到1的时候,b更新为0,a更新为0,就是 00 的状态,相当于重置了;最后的结果保存在b中,明白了上面的分析过程,就能写出代码如下;
解法三:
class Solution {public:int singleNumber(vector& nums) {int a = 0, b = 0; for (int i = 0; i < nums.size(); ++i) {b = (b ^ nums[i]) & ~a; a = (a ^ nums[i]) & ~b; }return b; }};
【C++实现LeetCode(137.单独的数字之二)】到此这篇关于C++实现LeetCode(137.单独的数字之二)的文章就介绍到这了,更多相关C++实现单独的数字之二内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- MybatisPlus使用queryWrapper如何实现复杂查询
- python学习之|python学习之 实现QQ自动发送消息
- 孩子不是实现父母欲望的工具——林哈夫
- opencv|opencv C++模板匹配的简单实现
- Node.js中readline模块实现终端输入
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- java中如何实现重建二叉树
- leetcode|leetcode 92. 反转链表 II
- 人脸识别|【人脸识别系列】| 实现自动化妆