共计 711 个字符,预计需要花费 2 分钟才能阅读完成。
题目
数组 nums 蕴含从 0 到 n 的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有方法在 O(n) 工夫内实现吗?
留神:本题绝对书上原题稍作改变
示例 1:
输出:[3,0,1]
输入:2
示例 2:
输出:[9,6,4,2,3,5,7,0,1]
输入:8
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解释
数组中蕴含 0 到 n 所有整数,但就短少了一个,所以,针对这个问题有下列办法给出:
办法 1:求和求差法
- 先计算 0 - n 所有数之和。
- 再计算数组中所有元素之和。
- 做差
代码如下:
`
求和法
int n = numsSize+1;
int ret1= 0;
for(int i = 0; i<n; ++i)
{ret1 += i;//sum}
int ret2 = 0;
for(int j = 0; j<numsSize; ++j)
{ret2 +=nums[j];//sum of array
}
return ret1-ret2;
`
办法 2:位运算法
思路:应用位运算的异或运算来排除。
- 数组中元素 0 - n 短少一个。
- 在造一组数 0 -n。
- 后面两组数全副异或,后果就是所求的短少的数。
代码如下:
`
// 位运算
int x = 0;
for(int i = 0;i<numsSize+1; ++i)
{x^=i;// x 先和所有数异或一次}
for(int j = 0;j<numsSize; ++j)
{x ^= nums[j];// 持续异或数组中所有元素
}
return x;
`
总结
针对此类问题,求和求差法体现了数学的思维,位运算的奇妙在于能够应用异或去除反复两次呈现的数,最初剩下的数天然就是呈现一次的数。
如若各路大神还有更好的思路,请分享。
正文完