C liner time solution


  • 0

    Swap the numbers i to the place i-1 unless nums[i] == i+1.
    Then we can go through the array to find all the missing numbers.

    int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
        int *missed = malloc(sizeof(int) * numsSize);
        int idx = 0;
        for(int i=0; i<numsSize; ++i){
            while(nums[i]!=i+1 && nums[nums[i]-1]!=nums[i]){
                swap(nums, i, nums[i]-1);
            }
        }
        
        for(int i=0; i<numsSize; ++i){
            if(nums[i] != i+1)
                missed[idx++] = i+1;
        }
        
        *returnSize = idx;
        return missed;
    }
    
    void swap(int *nums, int a, int b){
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    

Log in to reply
 

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