Java - Tortoise and Hare are BFF. - 1ms


  • 0
    D

    Using Java's Arrays.sort is simpler, but this is algorithm was faster (1ms) and more fun to study and learn. See: https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

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

  • 0
    D

    Using java's Arrays.sort is a simpler option. But this was faster and more fun to learn.


Log in to reply
 

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