448. Find All Numbers Disappeared in an Array
An example of using vector<bool>
Problem statement
Given an array nums
of n
integers where nums[i]
is in the range [1, n]
, return an array of all the integers in the range [1, n]
that do not appear in nums
.
Example 1
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Example 2
Input: nums = [1,1]
Output: [2]
Constraints
n == nums.length
.1 <= n <= 10^5
.1 <= nums[i] <= n
.
Follow up
Could you do it without extra space and in O(n)
runtime? You may assume the returned list does not count as extra space.
Solution: Marking the appearances
#include <vector>
#include <iostream>
using namespace std;
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<bool> exist(nums.size() + 1, false);
for (auto& i : nums) {
exist[i] = true;
}
vector<int> result;
for (int i = 1; i <= nums.size(); i++) {
if (!exist[i]) {
result.push_back(i);
}
}
return result;
}
void print(vector<int>& nums) {
cout << "[";
for (auto& n : nums) {
cout << n << ",";
}
cout << "]\n";
}
int main() {
vector<int> nums = {4,3,2,7,8,2,3,1};
auto result = findDisappearedNumbers(nums);
print(result);
nums = {1,1};
result = findDisappearedNumbers(nums);
print(result);
}
Output:
[5,6,]
[2,]
Complexity
Runtime:
O(N)
, whereN = nums.length
.Extra space:
O(1)
(vector<bool>
is optimized for space efficiency).
References
Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.
Did you find this article valuable?
Support LeetSolve by becoming a sponsor. Any amount is appreciated!