LeetCode 268. Missing Number题解

题目链接： 点击打开链接  题目要求算法的时间复杂度为O(N)，空间复杂度为O(1).  解题思路：输入序列为0...n（乱序）缺少其中一个数，所以数组的长度为n。举例来说，对于array[0]，经过一次替换可以将它换到正确的位置；但是新替换过来的array[0]可能未必是0，继续将新的array[0]替换到正确位置....如此继续。最终最大的数n会被换到缺少的数字对应的位置，其他数组都被替换到正确位置。 举例来说，如果输入序列为[3,5,0,4,1,6] 第一次替换后数组变为：[4,5,0,3,1,6] 第二次替换后数组变为：[1,5,0,3,4,6] 第三次替换后数组变为：[5,1,0,3,4,6] 第四次替换后数组变为：[6,1,0,3,4,5] 此时注意到array[0]为6，而它在数组中并没有正确的下标对应，故暂时无法再替换。此时，除了6和0，其他数字均已经在正确位置。 接下来，array[1]=1，已在正确位置，继续 第五次替换后数组变为：[0,1,6,3,4,5] 此时只有最大的数6所处的位置不正确，而6所在的位置即为缺失的数应该在的位置。 每一次替换都能够将一个数移动到它的正确位置，因此满足时间复杂度为O(N)。 Java代码如下： public class Solution { public int missingNumber(int[] nums) { int tmp = 0; for (int i = 0; i < nums.length; i++) { while(nums[i] != i && nums[i]<nums.length){ int rightIndex = nums[i]; if (rightIndex < nums.length) { // 交换两值 tmp = nums[rightIndex]; nums[rightIndex] = nums[i]; nums[i] = tmp; } } } int i=0; for(; i<nums.length; i++){ if(nums[i] != i){ return i; } } return i; } }