问题描述
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?
原问题链接:https://oj.leetcode.com/problems/single-number-ii/
问题分析
其实这个问题本身并不复杂,它只是注明在一个数组里有一个数字出现了一次而其他的数字都出现了3次。为了记录这个数字,我们可以采用这样的一种思路。假定这里的所有数字都是32位的整数。那么它们每个数字对应的二进制表示就对应着一个32位里面某些位设置为1。而既然有的数字它们重复了3次。如果我们对这些每位出现1的个数进行统计,所有这些出现3次的数字它们对应的这个位的统计数为3的倍数。而例外的那个元素它在对应的位置出现了仅一次。当然,如果把它们为1的各个位置次数都累加起来,会有一些重叠的情况。比如说这个特殊的数字和其他数字在某个位都是1。
通过上述的累加,每个位为1的数字累加无非为以下几个情况。1.该位为所有出现3次数字的累加。这个时候,这个位的累加值必然是3的倍数,即3 * n。 2. 该位为出现3次的数字和这个特殊数字重叠的位置。这样,针对这个位置出现的1的次数为3 * n + 1。 3.该位仅仅是这个特殊数字的位置。这样,这个位置的值为1。 所以,如果要最后只保留这个特殊数字的位该怎么办呢?只要将每个位置的数字对3取模不就得到了么?
所以,我们可以很容易得到一个如下的代码:
public int singleNumber(int[] A) { if(A == null || A.length == 0) return 0; int[] a = new int[32]; for(int i = 0; i < A.length; i++) { for(int j = 0; j < 32; j++) { if((A[i] & (1 << j)) > 0) a[j] = (a[j] + 1) % 3; } } int result = 0; for(int i = 0; i < 32; i++) { if(a[i] > 0) result |= (a[i] << i); } return result; }
在上面的代码里,我们创建一个in[32]的数组。里面每个元素对应整数的一个位。然后我们遍历数组里的每个元素,针对这个元素的每个位和1 << j进行与运算。如果结果大于0,则将该位置的数字加1并对3求模。然后在得到的结果数组里在和0针对每一位进行或运算来恢复这个数字。这里我们依据的是一个数字和当前偏移的i位数字比如1 << i的与运算结果是大于0的。
粗粗看来,上面的代码是没问题的。可是如果我们实际中去运行的话,会发现有错误。而且这个错误看起来还不是那么明显。这个问题在哪里呢?我们前面代码里有for(int j = 0; j < 32; j++) (A[i] & (1 << j )) > 0 这个部分。问题就出在这里。当j比较小的时候,确实1 << j是大于0的。可是当j = 31的时候,1 << 31即2的31次方。我们知道,这个数字已经超过了int里最大的正数表示了。所以可以说它已经溢出了。如果在代码里尝试去打印输出1 << 31,输出的是一个负数。所以我们前面的代码结果里最高位会是0。为了修正这个问题,我们可以将前面代码里这个判断条件修改为:
for(int i = 0; i < A.length; i++) { for(int j = 0; j < 32; j++) { if((A[i] & (1 << j)) != 0) a[j] = (a[j] + 1) % 3; } }
或者倒过来,不是将当前的元素每个位和1左移若干位来比对。而是将这个元素向右移位,再和1进行与运算:
for(int i = 0; i < A.length; i++) { for(int j = 0; j < 32; j++) { if(((A[i] >> j) & 1) > 0) a[j] = (a[j] + 1) % 3; } }
这样,前面的代码就正确了。当然,我们的目标不仅仅是能够把代码写出来通过测试。如果能写的更加精炼一点更好。这个时候看前面的代码。在生成这个数字的各个位的时候,后面又要用到这个位的数字。我们完全可以将它们合并起来。这样修改后的代码如下:
public int singleNumber(int[] A) { int[] a = new int[32]; int result = 0; for(int i = 0; i < 32; i++) { for(int j = 0; j < A.length; j++) { if(((A[j] >> i) & 1) != 0) a[i] = (a[i] + 1) % 3; } result |= a[i] << i; } return result; }
总结
这个问题看似很简单,但是中间有一些小的细节还是应该非常小心的。不然很容易出错。需要注意的就是溢出和重新构造这个数字的过程。
相关推荐
扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出
LeetCode LeetCode题解 传送门 # 标题 解决方案 困难 笔记 1个 简单的 ... Remove_Duplicates_From_Sorted_Array_II ... Best_Time_To_Buy_And_Sell_StockII ... Single_NumberII Java 中等的 167 Two_Sum_II_Input_
136_single_number.py # 位操作:异或(xor)操作 x ^ 0 = x; x ^ x = 0 sum 001_two_sum.py # 求list中能加和成指定值的两个位置 015_3_sum**.py # 求list中能加和成0的三个值 数列 004_median_of_two_sorted_arrays....
preorder-traversal链表reorder-list链表linked-list-cycle-ii链表linked-list-cycle动态规划word-break-ii动态规划word-break链表copy-list-with-random-pointer复杂度single-number-ii复杂度single-number动态规划
SingleNumber 其他算法 各种SingleNumber变种 LinkListCycle I II 其他变种 编程之美 Preorder Traversal Inorder Traver sal postorder 非递归 不用栈! 字符串常用操作 字符串 各种转换 Pow(x,n) 优化 ...
II mod之后,可能数学公式就不能简单地给出答案了。但对我来说,其实和前一题没区别。动态规划处理这种问题,早就是牛刀杀鸡了。。 Single Number 碰巧我知道异或的解法。如果不知道的话,想想还是有点费事的。 ...
dna匹配 leetcode leetcode刷题--C++ ...Single Number 异或 Copy List with Random Pointer 单链表 map Max Points on a Line 斜率 map, int> Fraction to Recurring Decimal map long long 正负号 Repeated DNA S
Single Number 52.2% Easy 371 两个整数的和 51.6% Easy 104 二叉树的最大深度 50.1% Easy 325% Add the Easy 389.数字 49.9% 简单 226 反转二叉树 48.9% 简单 283 移动零点 46.9% 简单 404 左叶总和 45.5% 简单 383...
singleNumber ( self , nums : List [ int ]) -> int : 它是所谓的“类型提示”(或“函数注释”;自 Python 3.0 起可用)。 -> List[int] 意味着函数应该返回一个整数列表。 nums: List[int], target: int 表示 ...
leetcode添加元素使和等于 LeetCode LeetCode Record 归并快排的区别: 思想不同:归并从局部到整体,快排...single out the missing number. How? First, we need to understand the properties of XOR: firstly, XOR'
颜色分类leetcode leetcode.etc My solutions of the problems in Online judge website, leetcode, lintcode, etc. leetcode: 13 problems solved lintcode: 49 problems solved Title URL Solution Difficulty ...
number. 向后遍历数组,直到获得两个数的和是给定的值 You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single...
137 | [Single Number II](https://leetcode.com/problems/single-number-ii/) | [C++](./C++/single-number-ii.cpp) [Python](./Python/single-number-ii.py) | _O(n)_ | _O(1)_ | Medium ||| 190 | [Reverse Bits]...
leetcode 答案leetcode-java leetcode.com ...II Remove Duplicates from Sorted List com.leetcode.string Single Number com.leetcode.tree Balanced Binary Tree Maximum Depth of Binary Tree Same Tree
Leetcode的ac是什么意思 LeetCodeInJava List #98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #122 Best Time to Buy and Sell Stock II #136 Single Number #150 Evaluate ...
The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading ...
leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...
https://leetcode.com/problems/single-number/ level : - easy tags : - recursive - linked list solutions : - reverseList - runtime : 52 ms, beats 99.80% - memory : 35 MB, beats 47.37% - ...
lru缓存leetcode 力扣_30天 力扣 30 天挑战赛 日 问题描述 问题和解决方案链接 Git 解决方案页面 1 SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ...
leetcode 2 Naphda 编码面试研究 免责声明 该部门不隶属于 Slack 的实际管理部门,是衍生自 Slack 频道内部的独立小组。 内容 如何使用 问题清单 帮助更新 如何使用 简单的。 在 fork 这个仓库之后,在它前面发布你...