LC41. 缺失的第一个正数(妙)

题目大意

解题思路

• 排序nlogn，从1开始找，idx 第一个正数 for(i=idx)nums[i-1] == i ?
• O(N),但是空间也是O(N)，用桶标记，其实类似桶排序。

我思考到了原地修改打标记，但是忘了原本就是负数的怎么打标记？
题解说，由于nums.length的限制，所以我们可以将负数+x将其变为不影响结果的正数。首先负数本身就对结果没有影响。

答案一定是[1.nums.length()]。

Code

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int i=0;i<nums.size();i++) 
            if (nums[i] <= 0) nums[i] = 5e5+5;
        for (int i=0;i<nums.size();i++) {
            int t = abs(nums[i]);
            if (t <= nums.size()) {
                if (nums[t-1] > 0)  //忘记了 重复元素
                    nums[t-1] *= -1;
            }
        }
        int ans = nums.size()+1;
        for (int i=0;i<nums.size();i++) {
            if (nums[i] > 0) {
                ans = i+1;
                break;
            }
        }
        return ans;
    }
};