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.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
Use array index as the numbers.
public class Solution { public int missingNumber(int[] nums) { int len = nums.length; int lenIndex = -1; for(int i = 0; i< len; ++i) { while(nums[i] != i && nums[i] != len) { int index = nums[i]; int swap = nums[index]; nums[index] = nums[i]; nums[i] = swap; } if(nums[i] == len) lenIndex = i; } if(lenIndex == -1) return len; else return lenIndex; } }
Bit Solution: XOR collecting all numbers and indices. Only the number that appears only once will be left.
public class Solution { public int missingNumber(int[] nums) { int xor = 0, i = 0; for (i = 0; i < nums.length; i++) { xor = xor ^ i ^ nums[i]; } return xor ^ i; } }
原文：http://www.cnblogs.com/neweracoding/p/5470432.html