Given an array containing n distinct numbers taken from
0, 1, 2, ..., n
, find the one that is missing from the array.
Example 1:
Input: [3,0,1] Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1] Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Java Solution :
class Solution {
public int missingNumber(int[] nums) {
if(nums == null || nums.length < 1)
return 0;
Arrays.sort(nums);
int n = nums[nums.length-1];
int sum = (n*(n+1))/2;
int result = 0;
for(int i=0;i<nums.length;i++)
result+=nums[i];
if(result == sum && nums[0]==0)
return nums[nums.length-1]+1;
return sum-result;
}
}
No comments:
Post a Comment