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?


Log in to reply
 

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