Find the Missing Number 196

Question

Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.

Example

Given N = 3 and the array [0, 1, 3], return 2.

Challenge

Do it in-place with O(1) extra memory and O(n) time.

Solution

这道题和first missing positive number思想一样。

遍历数组，看当前位置上的数和其下标是否一致，若不一致，则将该数和正确下标位置上的数交换，然后继续检查新来的数，直到满足条件为止。

最后重新遍历数组，找到第一个下标和数不一致的下标返回即可。若全部满足，则返回下标最大值＋1，即数组长度。

代码如下：

public class Solution {
    /**    
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        // write your code here
        //和first missing positive number思想一样。遍历数组，看当前位置上的数和其下标是否一致，若不一致，则将该数和正确下标位置上的数交换，然后继续检查新来的数，直到满足条件为止。
        if(nums == null || nums.length == 0){
            return 0;
        }

        for(int i = 0; i < nums.length; i++){
            while(nums[i] != i && nums[i] < nums.length){
                //index为num[i]因该被放到的位置
                int index = nums[i];
                //若要放到的位置上已经有正确的数则不交换
                if(nums[index] == nums[i]){
                    break;
                }
                int temp = nums[i];
                nums[i] = nums[index];
                nums[index] = temp;
            }
        }

        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i){
                return i;
            }
        }

        return nums.length;
    }
}