41. First Missing Positive.md

41. First Missing Positive

---

leetcode-cn Daily Challenge on June 27, 2020.

leetcode Daily Challenge on September 30th, 2020.

---

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note:

• Your algorithm should run in O(n) time and uses constant extra space.

---

Solution

• mine

  • Java

    got form the discuss Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.5 MB, less than 6.85% of Java online submissions

    //O(N)time O(1)space
    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length == 0){
            return 1;
        }
        //get the positive count and move to head
        int positiveCount = movePositiveToHead(nums);
         //if no positive, return 1
        if(positiveCount < 1){
            return 1;
        }
        //set the positive index number to negetive
        for(int i = 0; i < positiveCount; i++){
            int t = Math.abs(nums[i]);
            if(t - 1 < positiveCount && nums[t - 1] > 0){
                nums[t - 1] = -nums[t - 1];
            }
        }
        //find index of the first positive value, and return index+1
        for(int i = 0; i < positiveCount; i++){
            if(nums[i] > 0){
                return i + 1;
            }
        }
        //all number is negetive, so we return positiveCount + 1
        return positiveCount + 1;
    }
    
    int movePositiveToHead(int[] nums){
        int index = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                swap(nums, i, index);
                index++;
            }
        }
        return index;
    }
    
    void swap(int[] nums, int src, int dst){
        if(src == dst){
            return;
        }
        int t = nums[src];
        nums[src] = nums[dst];
        nums[dst] = t;
    }
    

---

• the most votes

  Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.9 MB, less than 6.85% of Java online submissions

  //O(N)time O(1)space
  public int firstMissingPositive(int[] nums) {
      int n = nums.length;
  
      // 1. mark numbers (num < 0) and (num > n) with a special marker number (n+1) 
      // (we can ignore those because if all number are > n then we'll simply return 1)
      for (int i = 0; i < n; i++) {
          if (nums[i] <= 0 || nums[i] > n) {
              nums[i] = n + 1;
          }
      }
      // note: all number in the array are now positive, and on the range 1..n+1
  
      // 2. mark each cell appearing in the array, by converting the index for that number to negative
      for (int i = 0; i < n; i++) {
          int num = Math.abs(nums[i]);
          if (num > n) {
              continue;
          }
          num--; // -1 for zero index based array (so the number 1 will be at pos 0)
          if (nums[num] > 0) { // prevents double negative operations
              nums[num] = -1 * nums[num];
          }
      }
  
      // 3. find the first cell which isn't negative (doesn't appear in the array)
      for (int i = 0; i < n; i++) {
          if (nums[i] >= 0) {
              return i + 1;
          }
      }
  
      // 4. no positive numbers were found, which means the array contains all numbers 1..n
      return n + 1;
  }
  

---