//

// Solution41.cpp

// Algorithm

//

// Created by Pancf on 2020/10/18.

// Copyright © 2020 Pancf. All rights reserved.

//

#include "Solution41.hpp"

int Solution41::firstMissingPositive(std::vector<int> &nums)

{

// nums.size() <= 300, -2^31 <= nums[i] <= 2^31 - 1

// 要求时间复杂度为o(n)，空间复杂度为常量，也就是说只能遍历一次nums

// 如何保存遍历过的元素信息是关键

// 因为nums.size() <= 300，因此第一个缺失的正整数一定 <= 301

uint32_t fields[10] = {0}; // can store 320 elements info

for (auto num : nums) {

if (0 < num && num < 301) {

// store 1~32 in filed[0], 33~64 in field[1], 65~96 in field[2]

int index = (num - 1) / 32;

int shift = (num - 1) % 32;

fields[index] = fields[index] | (1 << shift);

}

}

int index = 0;

for (int i = 0; i < 10; ++i) {

// field[i] contains 0 in some bit

if (fields[i] ^ 0xFFFFFFFF) {

index = i;

break;

}

}

int res = index * 32;

auto field = fields[index];

index = 1;

// find 0 in field

while (field & 0x1) {

++index;

field = field >> 1;

}

res += index;

return res;

}