<p>
268. Missing Number
Total Accepted: 60895
Total Submissions: 147019
Difficulty: Medium
Given an array containing n distinct numbers taken from0, 1, 2, ..., n
, find the one that is missing from the array.
For example,Given nums =[0, 1, 3]
return2
.
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.
</p>
方法一
<code>
public class MissingNumber268 {
public int missingNumber(int[] nums) {
int absence=0;
int temp[] = new int[nums.length+1];
for(int i=0;i<nums.length;i++){
temp[nums[i]] =1;
}
for(int i=0;i<temp.length;i++){
if(temp[i]!=1){
absence = i;
}
}
return absence;
}
public static void main(String[] args){
int nums[] = {0,1,3};
MissingNumber268 mn = new MissingNumber268();
System.out.println(mn.missingNumber(nums));
}
}
</code>
方法二 （better）
<code>
public int missingNumber(int[] nums) {
int absence = 0;
int total = 0;
for (int i = 0; i < nums.length; i++) {
total += nums[i];
}
absence = (1 + nums.length) * nums.length / 2 - total;
return absence;
}
</code>
