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.


  • 0
    K
    /**
     * Return an array of size *returnSize.
     * Note: The returned array must be malloced, assume caller calls free().
     */
    

    According to the requirements, caller calls free(). The returned pointer in this case to &histogram[1] is not a valid pointer to be freed.

    Instead of using histogram[0] as the counter, can use (*returnSize) instead, allowing the return array to start at histogram[0] and can simply return histogram;.


Log in to reply
 

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