題目

給你一個(gè)未排序的整數(shù)數(shù)組 nums ，請(qǐng)你找出其中沒有出現(xiàn)的最小的正整數(shù)。

請(qǐng)你實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 并且只使用常數(shù)級(jí)別額外空間的解決方案。示例 1：輸入：nums = [1,2,0]
輸出：3
示例 2：輸入：nums = [3,4,-1,1]
輸出：2
示例 3：輸入：nums = [7,8,9,11,12]
輸出：1提示：1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

解決思路

借用map 就可以實(shí)現(xiàn)，但是如果不借用map，在原空間上，也可以實(shí)現(xiàn)，不過想要使用原來的數(shù)據(jù)，會(huì)有侵略性，會(huì)把原來的數(shù)據(jù)修改掉。

解決方法

方法一：

    fun firstMissingPositive(nums: IntArray): Int {val size = nums.sizenums.forEachIndexed { index, i ->if (i <= 0) {nums[index] = size + 1}}nums.forEachIndexed { index, i ->if (i.absoluteValue in 1..size && nums[i.absoluteValue -1]  > 0) {nums[i.absoluteValue -1] = -nums[i.absoluteValue -1]}}nums.forEachIndexed { index, i ->if (i >= 0){return index + 1}}return size + 1}

方法二：

    fun firstMissingPositive2(nums: IntArray): Int {val size = nums.sizevar temp = 0nums.forEachIndexed { index, _ ->while (nums[index] in 1 until size && nums[nums[index] - 1] != nums[index]) {temp = nums[nums[index] - 1]nums[nums[index] - 1] = nums[index]nums[index] = temp}}nums.forEachIndexed { index, i ->if (index != i - 1) {return index + 1}}return size + 1}

總結(jié)

算法是很看一個(gè)人的思維邏輯的，所以很多都會(huì)考驗(yàn)一下算法。
算法確實(shí)重要。
做了快一年算法了，確實(shí) 學(xué)習(xí)如園中小草，不見其增，日有所長(zhǎng)
面試遇到算法就很輕松就過了