41. First Missing Positive

class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        
        int prev = 0;
        
        if (nums.length < 1) {
            return 1;
        }
        
        int loc = 0;
        
        while (loc < nums.length && nums[loc] <= 0) {
            loc++;
        }
        
        while (loc < nums.length) {
            if (nums[loc] <= 0) {
                loc++;
            } else if (nums[loc] == prev + 1) {
                loc++;
                prev++;
            } else if (nums[loc] == prev) {
                loc++;
            } else {
                break;
            }
        }
        
        return prev + 1;
        
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for First Missing Positive.
Memory Usage: 37 MB, less than 27.09% of Java online submissions for First Missing Positive.

전씨도 같은 루션이일거라는 점 믿어 의심치 않읍니다^^

sort ==> nlogn
while: n이니깐 nlogn에 포함
Memory: O(1)

class Solution {
  public int firstMissingPositive(int[] nums) {
    int n = nums.length;

    // Base case.
    int contains = 0;
    for (int i = 0; i < n; i++)
      if (nums[i] == 1) {
        contains++;
        break;
      }

    if (contains == 0)
      return 1;

    // nums = [1]
    if (n == 1)
      return 2;

    // Replace negative numbers, zeros,
    // and numbers larger than n by 1s.
    // After this convertion nums will contain 
    // only positive numbers.
    for (int i = 0; i < n; i++)
      if ((nums[i] <= 0) || (nums[i] > n))
        nums[i] = 1;

    // Use index as a hash key and number sign as a presence detector.
    // For example, if nums[1] is negative that means that number `1`
    // is present in the array. 
    // If nums[2] is positive - number 2 is missing.
    for (int i = 0; i < n; i++) {
      int a = Math.abs(nums[i]);
      // If you meet number a in the array - change the sign of a-th element.
      // Be careful with duplicates : do it only once.
      if (a == n)
        nums[0] = - Math.abs(nums[0]);
      else
        nums[a] = - Math.abs(nums[a]);
    }

    // Now the index of the first positive number 
    // is equal to first missing positive.
    for (int i = 1; i < n; i++) {
      if (nums[i] > 0)
        return i;
    }

    if (nums[0] > 0)
      return n;

    return n + 1;
  }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for First Missing Positive.
Memory Usage: 36.6 MB, less than 75.07% of Java online submissions for First Missing Positive.