Leecode热题100-41.缺失的第一个正数

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

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

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

解法都在代码注释里，看不懂的留言或者私信，看到第一时间解答

class Solution {
    /**假设我们的数是最理想的，一共有n个数，这n个数分别是1~n，分别放在0~n-1的位置上然后我们缺n+1,n+1就是第一个缺失的正数
    n就是我们有用的数的最大期望值
    但是我们遍历的过程中会发现一些比如是负数或者已经有过的有用的数或者大于n的数，那最大期望值就要-1了，因为现在已经有了一个没有用的值
    如果遇到位置不对的就交换到对的位置*/
    public int firstMissingPositive(int[] nums) {
        if(nums.length == 1) {
            return nums[0] == 1? 2 : 1;
        }
        /**定义最大期望值（最大的有用的值）*/
        int bestExpect = nums.length;
        /**已经确定的从1开始的连续区间的结尾*/
        int confirmedMax = 0;
        /**当前遍历的位置 */
        int cur = 0;
        /**bestExpect位置及以后都是无效的 */
        while(cur < bestExpect) {
            /**if条件的三段分别表示三种无效的数：1.小于等于已经确定的区间（包含小于0）2.大于最大期望值 3.它应该去的位置上的值和它一样  */
            if(nums[cur] == cur + 1) {
                /*如果在合适的位置扩大确定的区域 */
                cur ++;
                confirmedMax ++;
            } else if(nums[cur] <= confirmedMax || nums[cur] > bestExpect|| nums[nums[cur]-1] == nums[cur] ) {
                swap(nums, cur, --bestExpect);
            } else {
                /**有效但是不在自己该在的位置，回自己位置上去，这里cur不能++，因为它是换过来的应该继续考察 */
                swap(nums, cur, nums[cur] - 1);
            }
        }
        return confirmedMax + 1;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

原文地址：https://blog.csdn.net/Chang_Yafei/article/details/142730302

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！