Header Ad

Leetcode Find All Numbers Disappeared in an Array problem solution

In this Leetcode Find All Numbers Disappeared in an Array problem solution You are given 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.

Leetcode Find All Numbers Disappeared in an Array problem solution


Problem solution in Python.

def findDisappearedNumbers(nums: List[int]) -> List[int]:
    result = []
    for i in range(len(nums)):
        idx = abs(nums[i]) - 1
        nums[idx] = -abs(nums[idx])

    for i in range(len(nums)):
        if nums[i] < 0:  # to bring the input back to its original state
            nums[i] = -nums[i]
        else:  # found the missing number
            result.append(i + 1)
    return result



Problem solution in Java.

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {

        int[] temp=new int[nums.length+1];
        
        for(int i=0;i<nums.length;i++){
            temp[ nums[i] ]++;
        }
        
        List<Integer> list = new ArrayList<>();
        
        for(int i=1;i<temp.length;i++){
            if(temp[i]==0) list.add(i);
        }
        
        return list;
   }
}


Problem solution in C++.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) 
    {
        unordered_map<int, int> tempMap;
        vector<int> result;
        
        for(int  i =0; i < nums.size(); i++)
            tempMap.insert(pair<int, int>(nums[i] , 1));
        
        for(int i = 1; i <= nums.size(); i++)
        {
            if(!tempMap.count(i))
                result.push_back(i);
        }
        return result;
    }
};


Problem solution in C.

int partition(int* nums, int first, int last)
{
    int k = first;
    int i =0;
    int temp = 0;
    int pivot = nums[last];
    for(i=first;i<last;i++)
    {
        if(nums[i]<pivot)
        {
            temp = nums[k];
            nums[k] = nums[i];
            nums[i] = temp;
            k++;
        }
    }
    temp = nums[last];
    nums[last] = nums[k];
    nums[k] = temp;
   
    return k;
        
}


void qSort(int* nums, int first,int last)
{
    int threshold = 0;
    if(first<last)
    {
        threshold = partition(nums,first,last);
        qSort(nums,first,threshold-1);
        qSort(nums,threshold+1,last);
    }
}


int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
    
    int i=0,j=0;
    int* out = (int*)malloc(sizeof(int)*numsSize);
    int count  = 0;
    qSort(nums,0,numsSize-1);
    if(numsSize == 0)
    {
        *returnSize = count;
        return out;
    }
    for(i=1;i<nums[0];i++)
    {
        out[count] = i ;
        count++;
    }
    for(i=0;i<numsSize-1;i++)
    {
        for(j=nums[i];j<nums[i+1]-1;j++)
        {
            out[count] = j+1 ;
            count++;
        }
    }
    for(i=nums[numsSize-1];i<numsSize;i++)
    {
        out[count] = i+1 ;
        count++;
    }
    *returnSize = count;
    return out;
}


Post a Comment

0 Comments