Single Number
Given an array of integers, every element appearstwiceexcept for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Single Number II
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?
首先本能地想到一个算法,可是脑子一转,觉得是要O(n*n)时间复杂度。编译一下,果然没通过。程序如下:不过我觉得本算法最简单,而且通用性是最好的。
int singleNumber(int A[], int n) {
for(int i = 0; i < n; i++)
{
if(count(A, A + n, A[i])<2)
return i;
}
}
然后搜肠刮肚想想那个算法可以优化为时间O(n)的复杂度的?分治?减治?贪心?动态规划???想多了。
好吧,本能地分析吧:
1.要求复杂度为O(n),白话点说也就是不能在一个n次循环里面添加任何循环,前面之所以失败就是因为这个原因。但是可以在循环外添加循环!!!
2. 既然可以在查找循环外添加循环,那么添加什么循环好呢?排序吧,没错!排序的数列干什么都方便!(感觉这个结论也适用很多地方)
排序之后就可以很方便地计算一个数在数列中出现了多少次了。一连出现多少次就是总共出现多少次了,方便吧。O(∩_∩)O~
然后开始写代码了,wait!我觉得动手之前还是先考虑一下特殊情况吧。特殊情况一般是边界问题:
1. 如果数列外空呢?
2如果第一个是single number呢?
3如果最后一个是single number呢?
好了,分析完就可以写代码了!下面代码适合两个问题,只需要把出现次数修改为对应的2或3次数就可以了。而且不需要额外的空间!
//通用性好,适合两种情况
int singleNumber(int A[], int n) {
//特殊情况1,2
if(n<=0) return -1;
if(n==1) return A[0];
sort(A, A + n);
int j = 1;
for(int i = 0; i < n - 1; i++)
{
if(A[i] == A[i+1])
j++;
else
{
if(j<2) return A[i];//这里修改为j<3那么就可以适用于single number II了。
j = 1;
}
}
//特殊情况3 最后一个是single number的特殊情况
return A[n-1];
}
相对简单。
2014-3-6更新:
好了,更新不说通用性了。上面的基本排序处理的确是很通用的,属于基本算法内容了,没什么值得深入探讨的。
想不到这篇文章有幸可以有这么多人阅读。
这里更新下解说。
本题类型有三种解法的:
1 如上面的排序后处理的方法
2 利用map处理,效率也接近O(n)
3 位运算操作解法-这里也主要可以分两种解法
下面程序是利用unordered_map解Single number I的程序(Single number II是一样道理):
//2014-2-18 update
int singleNumber(int A[], int n)
{
unordered_map<int, bool> ump_ii;
for (int i = 0; i < n; i++)
{
if (!ump_ii.count(A[i])) ump_ii[A[i]] = true;
else ump_ii.erase(A[i]);
}
return ump_ii.begin()->first;
}
下面是Single number I 的位运算解法,思路就是每位bit出现2次就清零,所以可以不断异或运算得出最终结果:
//2014-2-18_2 update
int singleNumber(int A[], int n)
{
int ans = 0;
for (int i = 0; i < n; i++) ans ^= A[i];
return ans;
}
Single number II 的位运算两种解法-- 参考leetcode论坛的代码:
方法一,int的32个bit逐个处理-这个方法还算简单的了:
int singleNumberII_36(int A[], int n)
{
int ans = 0;
for (int i = 0; i < 32; i++)
{
int c = 0, d = 1<<i;
for (int j = 0; j < n; j++)
if (A[j] & d) c++;
if (c%3) ans |= d;
}
return ans;
}
方法二,进位,掩码清零法-本方法还是挺难理解的,要很小心,否则,很容易出错的,对位运算不熟悉是很难写出来的。
int singleNumber(int A[], int n)
{
int one = 0, two = 0;
for (int i = 0; i < n; i++)
{
two |= A[i] & one;//two 积累值
one ^= A[i];//one不断求反
int t = one & two;//第三次的时候one和two都保留了该位的值
one &= ~t;//清零出现三次的该位的值
two &= ~t;
}
return one;
}
好了,网上也有其他Single number II的变异的位运算算法,不过都不太好理解。Single NumberII可以说高达5星级难度了。
不过上面的位运算方法一还是算好理解的了,而且也比较容易就可以用在其他情况,比如所有numbers都出现5次其中一个除外,面试的时候我觉得应该是首推算法吧。
分享到:
相关推荐
LeetCode:LeetCode培训&&分享
扩展二:给定一个包含n个整数的数组,有一个整数x出现b次,一个整数y出现c次,其他所有的数均出现a次,其中b和c均不是a的倍数,找出x和y。中每一位二进制位1出
LeetCode Palindrome Number解决方案
leetcode04_寻找两个正序数组的中位数解法.rar !!!CSDN的一个特性: 即使我设置成免费下载,被下载的次数多了之后也会变成付C币下载的了,这个很头疼. !!!因此如果没有C币但想要下载的朋友可以在b站视频下留言给我,留下...
Solutions collection of LeetCode submissions in JavaScript & TypeScript (LeetCode 解题集之 JavaScript & TypeScript 版).zip
leetcode 答案 LeetCode-practice 记录在leetcode练习的代码&总结 #1TwoSum #26RemoveDuplicatesFromSortedArray #27RemoveElement #35SearchInsertPosition 最佳答案未解 Git使用练习 练习下分支切换&合并 解决...
Leetcode 92. 反转链表 II问题描述算法解法1: 递归图示解法1:实现def reverseBetween(self, head: ListNode
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]...
leetcodebook_leetcode 1~400知识点&题型总结&leetcode对应题表
leetcode 分类 leetcode 练习 按照数据结构和算法分类对leetcode题型做出解答 主要使用C/C++语言 每道题给出算法思路,示例,分析时间、空间复杂度,争取做到最优解 暂时就想到这么多,以后再添加吧^_^
leetcode 分类 LeetCode LeetCode上的算法题使用golang和c++实现 目录结构 c++ LeetCode [^使用说明]:使用vs2019打开此路径下的sln文件,LeetCode.cpp中main函数用于测试 go src [^分包说明]:按照不同类型的题目建包...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 ...
Leetcode two sum java 解法
Leetcode解答。所有的问题都支持C++语言,一部分问题支持Java语言。
Determine whether an integer is a palindrome. Do this without extra space. Java AC版本
来自leetcode的精选题目的多种解法详解,提高刷题效率。
Leetcode&Codewars问题 反向整数 两个总和获取总和反向字符串合并两个二叉树反向链接列表链结列表最长回文从排序数组中删除重复项有效括号 BST中的最小绝对差 DeleteNodeInLinkedList 包含重复的生成括号有效字谜...
因此在之后的刷题过程中,刻意放慢了脚步,每做完一道题,都去主动思考这种算法的时空复杂度是多少,是否还有更优的解法,能否做到举一反三等。 章节的编排形式参考了leetcode的题型分类,例如二叉树,字符串以及...