An accepted C# Solution with 3 step explanations


  • 0
    L
        public class Solution {
           //Idea is to move same integer to same index's value,
           //then loop the sorted array to decide first missing
                public int FirstMissingPositive(int[] nums)
                {
                    if (nums.Length == 0) return 1;
                    if (nums.Length == 1) return nums[0] == 1 ? 2 : 1;
                    int i = 0;
                    //Step 1: Move integer range (1, nums.Length) to make nums[i] == i if possible
                    //            nums[0] will be used to save nums.Length;
                    while (i < nums.Length)
                    {
                        if (nums[i] < 1 || nums[i] > nums.Length)
                        {
                            i++;
                            continue;
                        }
                        if (nums[i] == nums.Length)
                        {
                            if (nums[i] == nums[0])
                            {
                                if(i != 0) nums[i] = 0;
                                i++;
                            }
                            else
                            {
                                int tmp = nums[0];
                                nums[0] = nums[i];
                                nums[i] = tmp;
                            }
                        }
                        else if (nums[i] == i)
                            i++;
                        else
                        {
                            if (nums[i] == nums[nums[i]])
                            {
                                if (i != nums[i])
                                    nums[i] = 0;
        
                                i++;
                            }
                            else
                            {
                                int tmp2 = nums[nums[i]];
                                nums[nums[i]] = nums[i];
                                nums[i] = tmp2;
                            }
        
                        }
                    }
    
                    //Step 2: After it's sorted, find out the first index which is not 
                    //            assigned the same integer value.
                    for (i = 1; i < nums.Length; i++)
                        if (nums[i] < 1 || nums[i] > nums.Length - 1)
                            return i;
        
                    //Step 3: If from 1 to Nums.Length -1, it's all assigned with the same integer
                    //            then use nums[0] to make the final decision
                    return nums[0] == nums.Length ? nums.Length + 1 : nums.Length;
        
        
                }
        }

Log in to reply
 

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