Java two solutions with O(n) time and O(1) space


  • 2
    C
    public class Solution {
        /* marking all numbers present with negative indices*/
        public List<Integer> findDisappearedNumbers(int[] nums) {
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0; i<nums.length; i++){
                if(nums[Math.abs(nums[i])-1]>0){
                    nums[Math.abs(nums[i])-1] = - nums[Math.abs(nums[i])-1];
                }
            }
            for(int i=0; i<nums.length; i++){
                if(nums[i]>0){
                    list.add(i+1);
                }
            }
        return list;
    }
    /* repeatedly swapping till all nums are in correct position*/
    public List<Integer> findDisappearedNumbers(int[] nums) {
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0; i<nums.length; i++){
                int num = nums[i];
               while(num!=nums[num-1]){
                   int temp = nums[num-1];
                   nums[num-1] = nums[i];
                   nums[i] = temp;
                  num = nums[i];
               }
            }
            System.out.println(Arrays.toString(nums));
        for(int i=0; i<nums.length; i++){
            if(nums[i]!=i+1) list.add(i+1);
        }
        return list;
    }
    }
    

  • 0

    What is the runtime complexity of the 2nd solution?


  • 0
    L

    @dkarampi Hey, do you kown the xomplexity of the 2nd solution now?


Log in to reply
 

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