Missing Number

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

题意：从一组非负整数中找出缺少的数，比如[0,1,3]，缺少2

要求：时间复杂度O(N),空间复杂度O(1)

思考路线：

1） 第一想法是对数组排序，然后遍历一遍，但是时间复杂度O(nlogn)，不满足要求；

2） 接着想用map做，可以做到时间复杂度O(N),但是空间复杂度O(N)，不满足要求；

3） 针对第二个想法，由于不能用额外的空间存储，想到只能用目前已有的数组做map了，

      即数组既要能够保存原有数组的信息，又能实现map的功能。

思路：数组实现map功能，当然是数组下标做Key，数组元素做value。怎样表明数字存在，没有missing？若用额外的map做的话，我们会将map[key] 置为 1，这里我们将nums[key]置为其原有置为 -1 * nums[key]，这样在后面遍历的时候，可以通过乘上-1还原原数组的信息；第二次遍历，找到第一个不为负的数，即为missing的数字。

注意坑：对0的操作，由于乘上-1还为0，所有对于，要单独用标志。

代码：

public class Solution {
    public int missingNumber(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        int flag = -1 * Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++) {
            int index;
            if(nums[i] <= 0) {
                index = nums[i] * -1;
            } else {
                index = nums[i];
            }
            if(index == -1 * flag)
            	index = 0;
            if(index < nums.length) {
            	if(nums[index] == 0) {
            		nums[index] = flag;
            	} else {
                    nums[index] = -1 * nums[index];
            	}
            }
        }
        int j = 0;
        for(j = 0; j < nums.length; j++) {
        	if(nums[j] >= 0) {
        		break;
        	}
        }
        return j;
    }
}

Missing Number

原文：http://blog.csdn.net/tangximing123/article/details/49848533