Three different O(n) java solutions. The first two can be applied to the "First Missing Positive" problem.


  • 0
    L

    The idea is to put every element to where it is supposed to be at. They should be nums[i] = i. If not, then we swap. After finishing swapping, we can then check which number is missing. This idea can also be expanded to another similar problem "First Missing Positive". Even thought there is a two-layer loop. The time complexity is still O(n).

        public int missingNumber(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                while (nums[i] != i && nums[i] <= nums.length - 1) {
                    swap(nums, i, nums[i]);
                }
            }
            for (int i = 0; i < nums.length; i++) {
                if (i != nums[i]) {
                    return i;
                }
            }
            return nums.length;
        }
        
        public void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    

    The second solution uses hashset to see which one is not in the original array. Time complexity is O(n). This idea can also be expanded to another similar problem "First Missing Positive".

        public int missingNumber(int[] nums) {
            	HashSet set = new HashSet();
    	        for(int i = 0; i < nums.length; i++){
    	            set.add(nums[i]);
                }
                int missing = 0;
                for(int i = 0; i < nums.length + 1; i++ ){
    	            if(!set.contains(i)){
                        missing = i;	
                        break;
                    }
                }
                return missing;
        }
    

    This calculates the sum difference between the original array and what it supposed to be. The difference is the missing number. Time complexity is O(n).

        public int missingNumber(int[] nums) {
            	int sum = 0;
    	        int length = nums.length;
    	        for(int i = 0; i < length; i++){
    		        sum += nums[i];
                }
                return length * (length + 1) / 2 - sum;
        }
    

Log in to reply
 

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