C Solution (O(n) and no additional space)


  • 5
    V
    int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
        int* histogram = (int*) malloc(sizeof(int) * (numsSize + 1)); 
        memset(histogram, 0, sizeof(int) * numsSize);
    
        for (int index = 0; index < numsSize; index++) {
            histogram[nums[index]]++;
        }
    
        histogram[0] = 1;
        for (int index = 1; index <= numsSize; index++) {
            if (histogram[index] == 0) {
                histogram[histogram[0]] = index;
                histogram[0]++;
            }
        }
        *returnSize = histogram[0] - 1;
        return &histogram[1];
    }
    

    Keeping a histogram array, and later traversing the histogram to return elements with 0 values allows us to solve this problem with O(n) complexity. Index 0 of the histogram was used to store the number of missing numbers.


  • 0
    W

    a perfect solution!


  • 0
    M

    Your solution works fine when the array is in small size. Suppose the array size is 10^6, and only has one disappeared number. Your solution will allocate 4*10^6 bytes to hold data. But actually you only need 4 bytes.


  • 0
    D

    you malloc first, in my opinion, that's the addtional space the author means.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.