[LeetCode] Missing Number 丢失的数字
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n
, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3]
return 2
.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
这道题给我们n个数字,是0到n之间的数但是有一个数字去掉了,让我们寻找这个数字,要求线性的时间复杂度和常数级的空间复杂度。那么最直观的一个方法是用等差数列的求和公式求出0到n之间所有的数字之和,然后再遍历数组算出给定数字的累积和,然后做减法,差值就是丢失的那个数字,参见代码如下:
解法一:
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = , n = nums.size();
for (auto &a : nums) {
sum += a;
}
return 0.5 * n * (n + ) - sum;
}
};
这题还有一种解法,使用位操作Bit Manipulation来解的,用到了异或操作的特性,相似的题目有Single Number 单独的数字, Single Number II 单独的数字之二和Single Number III 单独的数字之三。那么思路是既然0到n之间少了一个数,我们将这个少了一个数的数组合0到n之间完整的数组异或一下,那么相同的数字都变为0了,剩下的就是少了的那个数字了,参加代码如下:
解法二:
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = ;
for (int i = ; i < nums.size(); ++i) {
res ^= (i + ) ^ nums[i];
}
return res;
}
};
这道题还可以用二分查找法来做,我们首先要对数组排序,然后我们用二分查找法算出中间元素的下标,然后用元素值和下标值之间做对比,如果元素值大于下标值,则说明缺失的数字在左边,此时将right赋为mid,反之则将left赋为mid+1。那么看到这里,作为读者的你可能会提出,排序的时间复杂度都不止O(n),何必要多此一举用二分查找,还不如用上面两种方法呢。对,你说的没错,但是在面试的时候,有可能人家给你的数组就是排好序的,那么此时用二分查找法肯定要优于上面两种方法,所以这种方法最好也要掌握以下~
解法三:
class Solution {
public:
int missingNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int left = , right = nums.size();
while (left < right) {
int mid = left + (right - left) / ;
if (nums[mid] > mid) right = mid;
else left = mid + ;
}
return right;
}
};
在CareerCup中有一道类似的题,5.7 Find Missing Integer 查找丢失的数,但是那道题不让我们直接访问整个int数字,而是只能访问其二进制表示数中的某一位,强行让我们使用位操作Bit Manipulation来解题,也是蛮有意思的一道题。
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- C#委托的一次";甜蜜";接触
- jetty9内嵌到应用,并在启动后加载WebApplicationInitializer,可运行jsp
- cglib动态代理
- Nim教程【七】
- Java 重写(Overriding)和重载(Overloading)
- 【POJ】1811 Prime Test
- PS1--cannot be loaded because the execution of scripts is disabled on this system
- Java中正则表达式、模式匹配与信息抽取
- jQuery对象与JS原生dom对象之间的转换
- 正斜杠和反斜杠-windows、web、c语言大讨论
- Topcoder Srm627 DIV 2
- android抓日志
- IDEA启动后页面没有tomcat server选项,显示灰色问号和红叉不能使用
- ESLint 的正式使用感受
- windows server 2008 R2 NPS(网络连接策略服务)设置radius,实现telent登陆交换机路由器权限分配
- Linux下通过vi修改只读文件
- node安装及配置之windows版
- LightOJ - 1356 Prime Independence (二分图 最大独立集 素数打表)
- window如何安装redis服务、卸载redis服务和启动redis服务
- 横竖屏切换时不销毁当前activity 和 锁定屏幕
热门文章
- PyQt4入门学习笔记(二)
- Redis简单案例(三) 连续登陆活动的简单实现
- 使用PD(PowerDesigner)图如何快速生成创建数据库表的SQL脚本
- [下载]北京新版小学英语五年级上册mp3点读APP
- 第四篇 Entity Framework Plus 之 Batch Operations
- C# 高效编程笔记1
- Delphi_06_Delphi_Object_Pascal_基本语法_04
- Aix/Linux下自动备份oracle数据库
- Linux下Weblogic创建域方法和步骤
- 漫谈Nuclear Web组件化入门篇