题解|#41. 缺失的第一个正数#

• 整数、求未出现的正整数。想到布隆过滤器
• 使用一个容器存储，如BitSet，将出现的数字添加进去

  寻找的为最小正数，所以数字的大小超过数组长度后，就不必添加了。无意义也避免内存溢出

• 然后从低到高循环直到找到为0的

package pers.sloera.leetcode.firstMissingPositive;

import java.util.BitSet;

/**
 * class pers.sloera.leetcode.firstMissingPositive
 * user sloera
 * date 2022/3/3
 */
public class Solution {
  public static void main(String[] args) {
    final Solution solution = new Solution();
    System.out.println(solution.firstMissingPositive(new int[]{1, 2, 0}));
    final int[] ints = new int[500000];
    for (int i = 0; i < ints.length; i++) {
      ints[i] = i;
    }
    System.out.println(solution.firstMissingPositive(ints));

  }
  public int firstMissingPositive(int[] nums) {
    final BitSet bitSet = new BitSet();
    for (int num : nums) {
      if (num > 0 && num <= nums.length) {
        bitSet.set(num);
      }
    }
    int res = 1;
    while (bitSet.get(res++));
    return res-1;
  }
}