深圳工程造价建设信息网站/网站设计公司哪家专业

题目

寻找缺失的数  

给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。

样例

N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。

注意

可以改变序列中数的位置。

挑战

在数组上原地完成，使用O(1)的额外空间和O(N)的时间。

解题

重新定义一个数组存放排序后的数，空间复杂度和时间复杂度都是O(N)

public class Solution {/**    * @param nums: an array of integers* @return: an integer*/public int findMissing(int[] nums) {// write your code hereboolean[] A = new boolean[nums.length +1];for(int i = 0;i<nums.length; i++){A[nums[i]] = true;}int n = 0;for(int i = 0;i< A.length ;i++){if(A[i] == false){n = i;break;}}return n;}
}

总耗时: 1674 ms

class Solution:# @param nums: a list of integers# @return: an integerdef findMissing(self, nums):# write your code hereA = [False]*(len(nums) + 1)for a in nums:A[a] = Truefor i in range(len(A)):if A[i] == False:return i

总耗时: 276 ms

在下面的挑战中，说可以在原始数组上面操作，如何在原始数组上面操作？空间复杂度并且是O(1) 

 i^i = 0 一个数自身的异或等于0

这个可以空间复杂可以是O(1),就有下面的代码了

public class Solution {/**    * @param nums: an array of integers* @return: an integer*/public int findMissing(int[] nums) {// write your code hereint res = 0;for( int i =0;i< nums.length ;i++){res = res ^ nums[i] ^ i;}res = res^(nums.length);return res;}
}

总耗时: 1802 ms

class Solution:# @param nums: a list of integers# @return: an integerdef findMissing(self, nums):# write your code hereres = 0for i in range(len(nums)):res = res ^ i ^ nums[i]res ^= len(nums)return res 

总耗时: 297 ms

在书影博客中看到通过求和来找缺失的数，我都被这个机智的方法吓到了，竟然如此如此的机智

直接复制其代码：

class Solution(object):def missingNumber(self, nums):""":type nums: List[int]:rtype: int"""n = len(nums)return n * (n + 1) / 2 - sum(nums)

 看到一个很牛逼的方法

在原始数组上，把A[i] 调整到其原来的位置 是的A[i] = i ，结束的地方就是当A[i] <0 此题目没有负数也没有影响的，A[i]>=n 显然的A[n]越界了。

以下面例子进行解释
[9,8,7,6,2,0,1,5,4]，是长度为9的数组，按照题目的要求应该是0到9十个数字，找出缺失的那一个。

第0下标，9>=9 不做交换,下面的输出是只对交换的情况，在输出当前交换前和交换后的情况 ，黄色标记是交换的两个元素

第1下标，A[1]!=1 A[1]与A[A[1]]进行交换，即 8 4交换
before: [9, 8, 7, 6, 2, 0, 1, 5, 4]later: [9, 4, 7, 6, 2, 0, 1, 5, 8]
交换后的A[1]依旧不等于1，继续A[1]与A[A[1]]交换，即 4 2 交换
before: [9, 4, 7, 6, 2, 0, 1, 5, 8]later: [9, 2, 7, 6, 4, 0, 1, 5, 8]
2 7 进行交换
before: [9, 2, 7, 6, 4, 0, 1, 5, 8]later: [9, 7, 2, 6, 4, 0, 1, 5, 8]
7 5 进行交换
before: [9, 7, 2, 6, 4, 0, 1, 5, 8]later: [9, 5, 2, 6, 4, 0, 1, 7, 8]
5 0 进行交换
before: [9, 5, 2, 6, 4, 0, 1, 7, 8]later: [9, 0, 2, 6, 4, 5, 1, 7, 8]
9 0 进行交换
before: [9, 0, 2, 6, 4, 5, 1, 7, 8]later: [0, 9, 2, 6, 4, 5, 1, 7, 8]
此时A[1]>=n 不进行交换
第2下标，A[2]=2不进行交换
第3下标，A[3]!=3,6 1 进行交换
before: [0, 9, 2, 6, 4, 5, 1, 7, 8]later: [0, 9, 2, 1, 4, 5, 6, 7, 8]
1 9 进行交换
before: [0, 9, 2, 1, 4, 5, 6, 7, 8]later: [0, 1, 2, 9, 4, 5, 6, 7, 8]
以后的下标都和其元素值相等，不需要交换

下面只需要遍历数组，找出下标和值不相等的点即可，当都满足的时候，说明是n值不在数组中

说明下，中间有个缺失的数，那么一定有个其他数字占据了他的位置，找到这个位置就是答案了。
可以看出在一次交换时候，至少把一个元素调整到其所在的下标位置，也就是A[tmp] = tmp 这个元素 ，而A[i] = A[tmp]之前的元素的值，不能保证每次都使得自己的元素回到自己的位置，所以要用while多次循环。

如下，好好体会：

public class Solution {/**    * @param A: an array of integers* @return: an integer*/public int findMissing(int[] A) {// write your code hereint n = A.length;for(int i = 0;i< n;i++){while( A[i] != i){if(A[i] <0 || A[i] >= n)break;int tmp = A[i];A[i] = A[tmp];A[tmp] = tmp;}}for(int i =0;i <n;i++){if(A[i] !=i)return i;}return n;}
}

 总耗时: 2141 ms

class Solution:# @param A: a list of integers# @return: an integerdef findMissing(self, A):# write your code heren = len(A)if A == None or n == 0:return 0# num0 = Afor i in range(n):while A[i] != i:# num0 = A[:]if A[i]<0 or A[i]>=n:breaktmp = A[i]A[i] = A[tmp]A[tmp] = tmp# if n > 6:# print 'before:',num0# print ' later:',Afor i in range(n):if A[i]!=i:return ireturn n

总耗时: 352 ms