【题目】
Given an array of integers, every element appearsthreetimes except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
【题意】
给定一个整数数组,每个元素出现了三次,除了一个。找出那个出现一次的数字。
注意:
你的算法应该在一个线性时间复杂度完成。你能不能无需使用额外的内存来完成它?
【思路一】
所有的数用二进制表示,我们把每个数的第i位取和之后再对3取余,那么只会有两个结果 0 或 1 。 如果为0代表只出现一次的那个数第i位也为0,
如果为1表示只出现一次的那个数第i位也为1。因此取余的结果就是那个 “Single Number”。
下面是一个直接用大小为 32的数组来记录所有 位上的和。
【代码一】
/*---------------------------------------
* 日期:2015-04-26
* 作者:SJF0115
* 题目: 137.Single Number II
* 网址:https://leetcode.com/problems/single-number-ii/
* 结果:AC
* 来源:LeetCode
* 博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int singleNumber(int A[], int n) {
int count[32] = {0};
int result = 0;
for(int i = 0;i < 32;++i){
for(int j = 0;j < n;++j){
if ((A[j] >> i) & 1) {
++count[i];
}//if
}//for
result |= ((count[i] % 3) << i);
}//for
return result;
}
};
int main(){
Solution solution;
int A[] = {2,3,4,2,5,2,3,3,5,5};
int result = solution.singleNumber(A,10);
// 输出
cout<<result<<endl;
return 0;
}
【思路二】
这个算法是有改进的空间的,可以使用掩码变量
方法 2:用 ones 记录到当前处理的元素为止,二进制 1 出现“1 次”(mod 3 之后的 1)的有哪些二进制位;
用 twos 记录到当前计算的变量为止,二进制 1 出现“2 次”(mod 3 之后的 2)的有哪些二进制位。
当 ones 和 twos 中的某一位同时为 1 时表示该二进制位上 1 出现了 3 次,此时需要清零。
即用二进制模拟三进制运算。最终 ones 记录的是最终结果。
【代码二】
/*---------------------------------------
* 日期:2015-04-26
* 作者:SJF0115
* 题目: 137.Single Number II
* 网址:https://leetcode.com/problems/single-number-ii/
* 结果:AC
* 来源:LeetCode
* 博客:
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int singleNumber(int A[], int n) {
int ones = 0, twos = 0, threes = 0;
for(int i = 0;i < n;++i){
// 出现2次
twos |= (ones & A[i]);
// 出现1次
ones ^= A[i];
// 当ones和twos中的某一位同时为1时表示该二进制位上1出现了3次
threes = ones & twos;
// 二进制位上1出现了3次此时ones和twos对应位上清零
ones &= ~threes;
twos &= ~threes;
}//for
return ones;
}
};
int main(){
Solution solution;
int A[] = {2,3,4,2,5,2,3,3,5,5};
int result = solution.singleNumber(A,10);
// 输出
cout<<result<<endl;
return 0;
}
分享到:
相关推荐
颜色分类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 ...
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]...
扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出
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....
leetcode 答案leetcode-java leetcode.com 的 Java 答案 ================索引================ com.leetcode.array Search a 2D Matrix Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II ...
LeetCode去除数组重复元素 Arithmetic-Swift 一些算法的swift实现 桶排序 冒泡排序 快速排序 ##正好看见LeetCode可以刷Swift的题目 开始慢慢刷 swift有playground 做起来还是相当方便的 已完成题目 ----2016.9.30 两...
LeetCode LeetCode题解 传送门 # 标题 解决方案 困难 笔记 1个 简单的 ... Remove_Duplicates_From_Sorted_Array_II ... Best_Time_To_Buy_And_Sell_StockII ... Single_NumberII Java 中等的 167 Two_Sum_II_Input_
leetcode添加元素使和等于 LeetcodePractice 用C++刷Leetcode题 2. Add Two Numbers You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order ...
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 ...
SingleNumber 其他算法 各种SingleNumber变种 LinkListCycle I II 其他变种 编程之美 Preorder Traversal Inorder Traver sal postorder 非递归 不用栈! 字符串常用操作 字符串 各种转换 Pow(x,n) 优化 ...
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动态规划
只出现一次的数字 题目 给定一个非空整数数组,除了某个元素只出现一次之外,其余每个元素均出现两次。找出那个只出现了一次的元素。... def singleNumber(self, nums: List[int]) -> int: a = 0 for i in n
leetcode 和 oj leetcode 尝试一些OJ。 412 Fizz Buzz 57.8% Easy 344 Reverse String 57.3% Easy 292 Nim Game 54.4% Easy 136 Single Number 52.2% Easy 371 两个整数的和 51.6% Easy 104 二叉树的最大深度 50.1% ...
leetcode添加元素使和等于 LeetCode LeetCode Record 归并快排的区别: 思想不同:归并从局部到整体,快排从整体到局部 稳定性:归并是稳定排序,快排不是稳定排序 运行时间:归并 $\Theta(n)logn$,快排只是平均...
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% - ...
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
leetcode 答案 leetcode 08/18 Unique Paths 应该是简单的数学排列组合问题,提炼一下其实就一句话:有m个黑球,n个白球,有多少种不同的排列方式。 我数学太差,没找到答案,直接上了动态规划。 Unique Paths II ...
singleNumber ( self , nums : List [ int ]) -> int : 它是所谓的“类型提示”(或“函数注释”;自 Python 3.0 起可用)。 -> List[int] 意味着函数应该返回一个整数列表。 nums: List[int], target: int 表示 ...
leetcode双人赛 工程共分为两个文件夹: A.Alogrithm 算法导论视频、书的相关程序,用于学习算法及数据结构的基础知识 B.Item 零基础学算法(戴艳) 的课后习题 C. leetcode的题目解答,按题目顺序进行排序 Given an...