Java solution, based on swapping elements


  • 1
    M

    The idea is pretty much similar to Question 41 , just reorganize elements by swapping elements to their correct positions. If the element is n, swapping will cause the array index out of bound, so I mark it as -1.

    public class Solution {
        public int missingNumber(int[] nums) {
            if(nums == null || nums.length == 0)
                return 0;
            int i = 0, n = nums.length;
            while(i < n){
                if(nums[i] == i)
                    i++;
                else if(nums[i] == n){
                    nums[i] = -1;
                    i++;
                }
                else if(nums[i] == -1)
                    i++;
                else
                    swap(nums, i, nums[i]);
            }
            for(int j = 0; j < n; j++){
                if(nums[j] == -1)
                    return j;
            }
            return n;
        }
        private void swap(int[] nums, int left, int right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
    }
    

Log in to reply
 

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