41. 缺失的第一个正数

https://leetcode-cn.com/problems/first-missing-positive/

Java

/*
 * @Author: Goog Tech
 * @Date: 2020-08-27 17:33:58
 * @LastEditTime: 2020-08-27 17:34:17
 * @Description: https://leetcode-cn.com/problems/first-missing-positive/
 * @FilePath: \leetcode-googtech\#41. First Missing Positive\Solution.java
 * @WebSite: https://algorithm.show/
 */

class Solution {

    // 原地修改法
    public int firstMissingPositive(int[] nums) {
        // 获取数组的长度
        int n = nums.length;
        // 遍历数组,将所有小于等于零的数修改成任意一个大于 N 的数,例如 N + 1
        for(int i = 0; i < n; i++) {
            if(nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        // 再次遍历数组,将数组中第 |x| - 1 位置上的数转换为负数
        for(int i = 0; i < n; i++) {
            // 取当前元素的绝对值
            int num = Math.abs(nums[i]);
            // 判断其值是否小于数组长度 n,若大于 n 则说明其原本为负数
            if(num <= n) {
                // 为了避免该指定下标的元素已经打了负号标记,首先取其绝对值,
                // 然后再通过重新赋值的方式将其转换为负数
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        // 最后遍历数组,若此时若数组中每一个数都为负数,那么答案为 N + 1
        // 否则答案就是第一个正数的位置上加一
        for(int i = 0; i < n; i++) {
            if(nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

Python

'''
Author: Goog Tech
Date: 2020-08-27 17:34:02
LastEditTime: 2020-08-27 17:34:43
Description: https://leetcode-cn.com/problems/first-missing-positive/
FilePath: \leetcode-googtech\#41. First Missing Positive\Solution.py
WebSite: https://algorithm.show/
'''

class Solution(object):

    # 原地修改法
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 获取数组的长度
        n = len(nums)
        # 遍历数组,将所有小于等于零的数修改成任意一个大于 N 的数,例如 N + 1
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n + 1
        # 再次遍历数组,将数组中第 |x| - 1 位置上的数转换为负数
        for i in range(n):
            # 取当前元素的绝对值
            num = abs(nums[i])
            # 判断其值是否小于数组长度 n,若大于 n 则说明其原本为负数
            if num <= n:
                # 为了避免该指定下标的元素已经打了负号标记,首先取其绝对值,
                # 然后再通过重新赋值的方式将其转换为负数
                nums[num - 1] = -abs(nums[num - 1])
        # 最后遍历数组,若此时若数组中每一个数都为负数,那么答案为 N + 1
        # 否则答案就是第一个正数的位置上加一
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        return n + 1