268. Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
- new solution update 2022.05.28
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int missingNumber(vector<int>& nums) {
nums.push_back(-1);
for(int i = 0; i < nums.size(); i++) {
if(nums[i] == -1) continue;
while(nums[i] != i and nums[i] != -1) {
swap(nums[i], nums[nums[i]]);
}
}
for(int i = 0; i < nums.size(); i++) {
if(nums[i] == -1) return i;
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int missingNumber(vector<int>& nums) {
unordered_set<int> num;
for(int i = 0; i <= nums.size(); i++)
num.insert(i);
for(auto& n : nums)
num.erase(n);
return *lower_bound(begin(num), end(num), 0);
}
};
|
