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 =
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?
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Solution 1: iterate the array, swap nums[i] to position i. Then iterate again, find the one which i!=nums[i], otherwise it is n.
public class Solution {
public int missingNumber(int[] nums) {
int n=nums.length;
for (int i=0; i<n; i++) {
while (nums[i]!=i && nums[i]<n) swap(nums,i,nums[i]);
}
for (int i=0; i<n; i++) {
if (i!=nums[i]) return i;
}
return n;
}
private void swap(int[] nums, int i, int j) {
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
没有评论:
发表评论