LeetCode.41.缺失的第一个正数（困难）

题目

LeetCode.41.缺失的第一个正数（困难）

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

题解

普通解法

• 如果用哈希表记录，空间复杂度超过O(1)。
• 如果用排序，时间复杂度超过O(n) 。

思路

• 虽然不能用排序，但是可以先看正常判断过程是怎样的，看能不能换一种方式达到同样的目的。
• 如果排序完了，从左到右遍历数组，如果发现nums[i] != i + 1，i + 1就是没有出现的最小正整数。
• 换句话说有没有办法不用排序也能把数组中i + 1这个数放到第i个位置存储，这样就能判断了。
• 可以在遍历的时候直接把数字放到对应位置上，只耗费常数级别时间复杂度。

具体实现

设nums数组长度为n，如果nums[i]是1到n之间的数，就把nums[i]放到nums[i] - 1的索引位置上。

这样从左到右遍历数组就可以知道没有出现的最小正整数是哪个了。

复杂度

时间复杂度O(n)

• 1到n之间的数交换到数组对应索引上只需要一次交换。
• 需要遍历整个数组检查每个元素是否在对应索引位置上。

空间复杂度O(1)

没有额外的空间开辟，只用了常数个变量。

class Solution {
    fun firstMissingPositive(nums: IntArray): Int {
        /*
        把1放到索引0
        把2放到索引1
        把3放到索引2
        把4放到索引3
        ...
        如[3,4,-1,1]
         */
        for (i in nums.indices) {
            while (nums[i] in 1..nums.size && nums[i] != nums[nums[i] - 1]) {
                nums.swap(i, nums[i] - 1)
            }
        }
        for (i in nums.indices) {
            if (nums[i] != i + 1) {
                return i + 1
            }
        }
        // 所求一定是在[1,n+1]之间
        // 如果是[1,2,3,4]，最小的就是n+1
        // 如果是[7,8,9,10]，最小的是1
        return nums.size + 1
    }
    
    private fun IntArray.swap(i: Int, j: Int) {
        val tmp = this[i]
        this[i] = this[j]
        this[j] = tmp
    }
}