关于数据结构和算法:消失的数字

30次阅读

共计 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:求和求差法

  1. 先计算 0 - n 所有数之和。
  2. 再计算数组中所有元素之和。
  3. 做差

代码如下:
`
求和法

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:位运算法

思路:应用位运算的异或运算来排除。

  1. 数组中元素 0 - n 短少一个。
  2. 在造一组数 0 -n。
  3. 后面两组数全副异或,后果就是所求的短少的数。

代码如下:
`
// 位运算

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;

`

总结

针对此类问题,求和求差法体现了数学的思维,位运算的奇妙在于能够应用异或去除反复两次呈现的数,最初剩下的数天然就是呈现一次的数。
如若各路大神还有更好的思路,请分享。

正文完
 0