C# solution: bucket sort


  • 0
    B

    Even if there is "while" in the loop, the time complexity is no more than 2n.

    I changed number to index at the beginning. So I do not need to do the transformation when I check the index.

    For example: inputs: [3, 4, -1, 1]

    // change to the index
    [2, 3, -2, 0]

    // start to compare with the index
    [-2, 3, 2, 0] (i = 0)
    [-2, 0, 2, 3] (i = 1)
    [0, -2, 2, 3] (i = 1)
    [0, -2, 2, 3] (i = 2)
    [0, -2, 2, 3] (i = 3)

    // find the first item which does not equal to the index
    find out -2 (i = 1)

    return i + 1 = 1 + 1 = 2

    public class Solution 
    {
        public int FirstMissingPositive(int[] nums) 
        {
            for (int i = 0; i < nums.Length; i++)
            {
                // Change the number to the index.
                nums[i]--;
            }
    
            for (int i = 0; i < nums.Length; i++)
            {
                while(0 <= nums[i] && nums[i] < nums.Length && i != nums[i])
                {
                    // Be careful! If we do not check, it may cause the infinite loop.
                    if (nums[nums[i]] == nums[i]) break;
                    
                    var temp = nums[nums[i]];
                    nums[nums[i]] = nums[i];
                    nums[i] = temp;
                }
            }
            
            for (int i = 0; i < nums.Length; i++)
            {
                // Find the first item which does not equal to the index.
                if (nums[i] != i)
                {
                    return i + 1;
                }           
            }
    
            return nums.Length + 1;
        }
    }
    

Log in to reply
 

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