Lintcode : 196. Missing Number

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

自己的思路:

public int findMissing(int[] nums) {int missingNum = 0;int sum = (nums.length+1) * (nums.length + 0)/2;for (int i = 0; i < nums.length; i++) {sum -= nums[i];}for (int num:nums) {sum -= num;}return sum;}

dalao思路

int findMissing2(int[] nums) {// write your code hereint N = nums.length;for (int i = 0; i < N; i++) {if (nums[i] != i && nums[i] < N) {int temp = nums[i];int temp1 = nums[nums[i]];nums[nums[i]] = temp;nums[i] = temp1;i--;}}for (int i = 0; i < N; i++) {if (nums[i] != i)return i;}return N;
}

dalao的解法在于因为i和a[i]是对应的，所以采取的贪心策略是每次都将i交换到他该在的位置

summary:i和a[i]对应的数组问题，可以考虑交换