findingsea's Studio.

First Missing Positive@LeetCode

LeetCode
Word count: 146 / Reading time: 1 min
2015/04/01 Share

First Missing Positive

同样是一道我不太能理解为什么能标为hard的题目。

我的解法是将所有正数都先放到map里面，然后就从小正数——也就是1——开始检查map，遇到的第一个不包含在map中的正数便是答案。最坏情况下的复杂度是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int firstMissingPositive(int[] A) {
        HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for (int a : A) {
            if (a > 0) {
                map.put(a, true);
            }
        }
        int v = 1;
        while (true) {
            if (!map.containsKey(v)) {
                break;
            }
            v++;
        }
        return v;
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/04/01/first-missing-positive/

发表日期: April 1st 2015, 9:21:00 am

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 100
2020
2019
2018
2017
2015
2014
2013
Octopress GitHub Python Django 吐槽 Reading ACM 项目总结 JavaScript 日志 Java LeetCode Interview Algorithm Life Windows ffmpeg life Go c++ essay review