上海做家庭影院的公司网站百度法务部联系方式

题目

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。示例 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 就可以实现，但是如果不借用map，在原空间上，也可以实现，不过想要使用原来的数据，会有侵略性，会把原来的数据修改掉。

解决方法

方法一：

    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}

总结

算法是很看一个人的思维逻辑的，所以很多都会考验一下算法。
算法确实重要。
做了快一年算法了，确实 学习如园中小草，不见其增，日有所长
面试遇到算法就很轻松就过了