This approach uses the properties of the array and its indices to track missing numbers. By iterating through the array and using the values to mark the corresponding indices, we can identify which indices were never marked and thus determine the missing numbers.
Steps:
nums.Time Complexity: O(n) - where n is the number of elements in the array because we are iterating over the array twice.
Space Complexity: O(1) - as no additional data structure is used apart from the output list and input array is modified in-place.
1#include <stdio.h>
2#include <stdlib.h>
3
4int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
5 for (int i = 0; i < numsSize; i++) {
6 int index = abs(nums[i]) - 1;
7 if (nums[index] > 0) {
8 nums[index] = -nums[index];
9 }
10 }
11
12 int* result = (int*)malloc(sizeof(int) * numsSize);
13 *returnSize = 0;
14 for (int i = 0; i < numsSize; i++) {
15 if (nums[i] > 0) {
16 result[(*returnSize)++] = i + 1;
17 }
18 }
19 return result;
20}This C solution implements index marking by negating the values at positions corresponding to the numbers seen in the array. It iterates over the array twice: first to mark visited numbers and second to collect those which are still positive, indicating those numbers are missing.
In this approach, we utilize a set to only store unique numbers from 1 to n that appear in the input array. By comparing this set to the complete range of numbers, we can directly determine those not present in the input.
Steps:
nums.Time Complexity: O(n)
Space Complexity: O(n), due to use of additional boolean array to track presence of numbers.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
6 bool* seen = calloc(numsSize + 1, sizeof(bool));
7 for (int i = 0; i < numsSize; i++) {
8 seen[nums[i]] = true;
9 }
10 int* result = malloc(numsSize * sizeof(int));
11 *returnSize = 0;
12 for (int i = 1; i <= numsSize; i++) {
13 if (!seen[i]) {
14 result[(*returnSize)++] = i;
15 }
16 }
17 free(seen);
18 return result;
19}In this solution, a boolean array acts as a set storing flags for numbers detected in the input. Subsequent traversal is made to seek indices flagged false, representing the missing numbers.