本文共 682 字,大约阅读时间需要 2 分钟。
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
. 注意这里并没有说给你的数组一定是有序的,只告诉你每一个数是不同的,而且只miss one;很容易想到的是sort一下,然后进行后一个元素减去前一个元素是否为1判断,这里注意对特殊情况,比如数组只有一个元素的时候,和[1,2,3]这种miss 0的情况。
另一种机智的思路是,数组的下标是0,1,2,3...nums.length-1,是固定的,数值也应是0,1,2,3,...nums.length-1,但是由于miss one 导致少了一个数他们变成了0,1,2...n,n-2...nums.length,可以发现除了少的那一个和因此多出来的nums.length其他都是成对出现的,所以只要把这些成对出现的数字消去,剩下的就是少的那个数和nums.length,再把nums.length去掉即可。
根据这种思路可以采取异或的方式,把所有的下标和数值异或,再和nums.length异或得到的就是那个miss one
int res = 0;int i = 0;for (; i < nums.length; i++) { res = res ^ i ^ nums[i]; }return res ^ i;
转载地址:http://shdvi.baihongyu.com/