My code:
public class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int n = nums.length;
int sum = (1 + n) * n / 2;
for (int i = 0; i < nums.length; i++)
sum -= nums[i];
return sum;
}
}
My test result:
这次题目感觉挺简单的，先用告诉公式算出总和，然后一个个减，失去的那个，就是最后sum还剩下的值。
然后网上看了，还有一种 bit manipulation的做法。感觉没必要啊，速度也没我快。
尽管我也不能理解他的算法。把代码贴在这里，以后有需要的时候可以看。
public class Solution {
public int missingNumber(int[] nums) {
int check = 0;
for (int i=0; i<nums.length; i++) {
check ^= nums[i] ^ i + 1;
}
return check;
}
}
**
总结： Array, bit manipulation
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0)
return -1;
int sum = 0;
for (int i = 0; i < nums.length; i++)
sum += nums[i];
int n = nums.length;
return (1 + n) * n / 2 - sum;
}
}
Anyway, Good luck, Richardo!
想多了，没想出怎么做。
原来如此简单。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int i = 0;
int pre = -1;
while (i < nums.length) {
if (nums[i] == nums.length) {
pre = i;
i++;
}
else if (nums[nums[i]] == nums[i]) {
i++;
}
else {
int temp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = temp;
}
}
if (pre == -1) {
return nums.length;
}
else {
return pre;
}
}
}
还可以这么做，虽然更复杂些。
Anyway, Good luck, Richardo! -- 09/12/2016
