268. Missing Number (Easy)
https://leetcode.com/problems/missing-number/
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?
Solutions
class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
int n = nums.length;
// n is the special case, check out whether it exists or not.
boolean nExists = false;
for (int i = 0; i < n; i++) {
if (nums[i] == n) {
nExists = true;
break;
}
}
// If not present, return it immediately.
if (!nExists) {
return n;
}
for (int i = 0; i < n; i++) {
if (nums[i] == n) {
continue;
}
if (nums[i] != i) {
// swap nums[i] to its corresponding slot
swap(nums, nums[i], i);
// do not move forward until current position is settled
i--;
}
}
// Finally, the slot of missing number will be swapped in n
for (int i = 0; i < n; i++) {
if (nums[i] != i) {
return i;
}
}
return -1;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}