LeetCode-困难进阶-41-缺失的第一个正数-原地解决(C)

这题是我解决的第一道困难的LeetCode，值得纪念。
而且还完成了进阶要求！

题目

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

进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？

示例 1：

输入：nums = [1,2,0]
输出：3
示例 2：

输入：nums = [3,4,-1,1]
输出：2
示例 3：

输入：nums = [7,8,9,11,12]
输出：1
 

提示：

0 <= nums.length <= 300
-231 <= nums[i] <= 231 - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 这题能满足进阶要求，但只是因为这题的nums[]数组大小有限，如果nums[]大小不限，这题无法满足常数项的额外空间。
• 这题是找最小未出现的正整数，那么如果nums[]的大小为numsSize，则最小未出现的正整数，一定在1~numsSize+1之间。
• 为了记录所有出现过的数，设置一个numsSize[]大小的hasAppeared[]数组，用来记录nums[]出现的数，且由于最小未出现正整数<=numsSize+1，hasAppeared[]只需要numsSize大小即可。
  • hasAppeared[n]里的值，表示n+1是否出现过，用1表示出现过，非1表示未出现过。
    • C语言中，未初始化的数组可能是随机值，也可能是0，这题在LeetCode的编译器里直接用1表示不会出现问题。
• 那么在代码里面只需要这么做即可：
  • 设置一个numsSize大小的hasAppeared[]数组。
  • 遍历nums[]，如果nums[pos]的值是<=numsSize的正整数，那么就将hasAppeared[ nums[pos]-1 ]的值置为1。
  • 遍历完nums[]后，再遍历hasAppeared[]，第一个非1的位置即是所求的未出现的最小正整数，如果全1，则是第numsSize+1为未出现的最小正整数。
• 例如：
  • 对于nums[] = {1, 0, 2};hasAppeared[]的情况为{1, 1, ?}。第一个非1位hasAppeared[2]，因此return 2+1，即pos+1
  • 对于nums[] = {1, 2, 3};hasAppeared[]的情况为{1, 1, 1}。全1，因此return 3+1，即numsSize+1。
    • 注：全1时的遍历结束后，pos == numsSize，因此两种情况均可return pos+1。
• 进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？
  • 代码时间复杂度为O(n)+O(n)，即O(n)。
  • 使用了n的不定空间。
    • 对于本题来说，numsSize不超过300，因此可以将长度为n的不定空间改成长度为300的空间，就可以满足进阶要求了。
  • 如果要实现原地解决的话，我的想法在现在的基础上改进：
    • 依然是遍历nums[]，如果0
    • 然后对nums[]执行如上hasAppeared的操作。
  • 是的，我想完想法发现好简单然后顺便实现了！
  • 现在是只需要两个int就能解决了！
  • 改进完发现原来的还缺点东西，新的思路是这样的：
    • 遍历nums[]，如果nums[pos] != pos+1，那么交换nums[pos]与nums[ nums[pos]-1 ]，并将pos--。
    • 结束后，遍历一遍nums[]，如果全符合nums[pos] == pos+1，就返回numsSize，否则返回pos+1。

代码-普通

/*
设置一个hasAppeared的int数组，大小为numsSize。
如果出现了这个数，就将hasAppeared置1，将nums[]遍历，
结束后，将hasAppeared遍历，如果全为1就表明1~numsSize全出现了，返回numsSize+1
否则返回第一个非1的。
*/

int firstMissingPositive(int* nums, int numsSize){
    int *hasAppeared = (int*)malloc(sizeof(int)*numsSize);
    int pos;
    for(pos=0;  pos<numsSize;   pos++){
        if(nums[pos]<=numsSize && nums[pos]>0) hasAppeared[ nums[pos]-1 ] = 1;
    }
    for(pos=0;  pos<numsSize;   pos++){
        if(hasAppeared[pos] != 1) return pos+1;
    }
    return pos+1;
}

代码-进阶

/*
遍历nums[]，如果nums[pos] != pos+1，那么交换nums[pos]与nums[ nums[pos]-1 ]，并将pos--。
结束后，遍历一遍nums[]，如果全符合nums[pos] == pos+1，就返回numsSize，否则返回pos+1。
*/

int firstMissingPositive(int* nums, int numsSize){
    int pos, temp;
    for(pos=0;  pos<numsSize;   pos++){
        if(nums[pos]<=numsSize && nums[pos]>0 && nums[pos]!=pos+1) {
            temp = nums[pos];
            nums[pos] = nums[ temp-1 ];
            nums[ temp-1 ] = temp;
            if(nums[pos] == nums[temp-1]) nums[pos]=-1;
            pos--;
        }
    }
    for(pos=0;  pos<numsSize;   pos++){
        if(nums[pos] != pos+1) return pos+1;
    }
    return pos+1;
}