LC41. First Missing Positive

작성일

문제: https://leetcode.com/problems/first-missing-positive/

  • Leet코드가 좋아하는 상위 bit에 정보 꾸겨넣는 문제
  • 풀이가 이것만 있는건 아니고 swap을 이용한 풀이도 있는듯
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int& n: nums) if(n <= 0) n = nums.size()+1;
        for (int n: nums)
            if(abs(n) <= nums.size() && nums[abs(n)-1] > 0)
                nums[abs(n)-1] *= -1;
        for (int i = 0; i < nums.size(); i++)
            if(nums[i] > 0)
                return i+1;
        return nums.size()+1;
    }
};