LeetCode第41题：First Missing Positive（Java、C++）详解

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode第41题：First Missing Positive（Java、C++）详解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2069字，纯文字阅读大概需要3分钟。

内容图文

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1

题目解析：
1、乍一看，题目很简单呀，但是限制了时间复杂度，题目就不简单啦，使用排序啥的肯定超时时间复杂度限制啦；
2、思路：
假设数组的大小为n，我们遍历整个数组，如果当前元素i在1-n之间那么就将当前元素和数组第i-1个元素交换。如果当前元素是负数或者大于n那么就不处理。
这样遍历完所有的元素之后，原始数组当中出现在1-n之间的元素都被放在了对应的0~n-1的位置里。再次遍历数组，找到第一个不满足nums[i]==i+1的位置，那么i+1就是最小的未出现的正整数。
解释：
nums[i]!=nums[nums[i]-1]
这句话的意思是：nums[i]表示数组第i个元素，如果是等于3，那么对应位置是不是放在nums[2]上面；
（因不能建立新的数组，那么只能覆盖原有数组，思路是把1放在数组第一个位置 nums[0]，2放在第二个位置 nums[1]，即需要把 nums[i] 放在 nums[nums[i] - 1]上）
3、一句话就是：把原有数组中值放在相应的位置上，最后遍历一次数组，就找到对应值啦。

C++代码：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //nums = [1,2,0];
        int n = nums.size();//n = 3;
        for (int i = 0; i < n; ++i) {
            //i = 0;
            //i = 1;
            //i = 2;
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            // 1 >0 ;1 <= 3;1 != 1 false
            // 2 > 0;2 <= 3;2 != 2 false
            // 0 > 0 false
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        //nums = [1,2,0]
        for (int i = 0; i < n; ++i) {
            //i = 0;
            //i = 1;
            //i = 2;
            if (nums[i] != i + 1) {
                //1 != 1;
                //2 != 2
                //0 != 3 true;
                return i + 1;
                //return 3
            }
        }
        return n + 1;
    }
};

Java代码：

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for(int i = 0;i<len;i++)
        {
            if(nums[i] == i + 1)
            {
                continue;
            }
            while(nums[i] > 0 && nums[i] <= len && nums[nums[i] -1] != nums[i])
            {
                swap(nums[i],nums[nums[i] - 1]);
            }
        }   
        for(int i = 0;i < len;i++)
        {
            if(nums[i] != i + 1)
            {
                return i + 1;
            }
        }
        return len + 1;
    }
    
    public void swap(int a,int b)
    {
        int temp = a;
        a = b;
        b  = temp;
    }
}

性能：
Java同样思路代码，显示超时，调试代码，在while处一直死循环，swap函数交换值，值未交换成功（这个地方需要深究下）；

总结：C++在性能上还是占优势的，Java调优需要进一步学习！

内容总结

以上是互联网集市为您收集整理的LeetCode第41题：First Missing Positive（Java、C++）详解全部内容，希望文章能够帮你解决LeetCode第41题：First Missing Positive（Java、C++）详解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端