LeetCode Missing Number
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: 2Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret;
int n = nums.size();
int checkout[n + 1];
for (int i = 0; i < n + 1; ++i) {
checkout[i] = 0;
}
for (int i = 0; i < n; ++i) {
checkout[nums[i]] = 1;
}
for (int i = 0; i < n + 1; ++i) {
if (!checkout[i]) {
ret = i;
break;
}
}
return ret;
}
};
class Solution {
public int missingNumber(int[] nums) {
int ret = 0;
int n = nums.length;
int[] checkout = new int[n + 1];
for (int i = 0; i < n + 1; ++i) {
checkout[i] = 0;
}
for (int i = 0; i < n; ++i) {
checkout[nums[i]] = 1;
}
for (int i = 0; i < n + 1; ++i) {
if (checkout[i] == 0) {
ret = i;
break;
}
}
return ret;
}
}
Copyright (c) 2020 CC-BY-NC-4.0 LICENSE