Two easy to understand O(n) solution based on HashSet and Swap.


  • 0
    L

    The code is pretty easy to understand.

        public int firstMissingPositive(int[] nums) {
            if(nums.length == 0){
                return 1;
            }
            HashSet set = new HashSet();
            int max = nums[0];
            for (int i = 0; i < nums.length; i++) {
                set.add(nums[i]);
                max = max > nums[i] ? max : nums[i];
            }
            for (int i = 1; i <= max + 1; i++) {
                if (!set.contains(i)) {
                    return i;
                }
            }
            return -1;
        }
    

    Another solution is to put every positive number into where they are supposed to be. They should be nums[i] = i + 1; If not, then swap. The inner while-loop makes sure every element gets a chance to be swapped, and nums[i] != nums[nums[i] - 1] makes sure there is no infinite loop.

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

Log in to reply
 

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