给定一个未排序的整数数组,找出其中没有出现的最小的正整数。要求时间复杂度 O(n),空间复杂度 O(1)。
第一行一个整数 n 表示数组长度,第二行 n 个整数(可能包含负数、零和正数)。
输出一个整数,表示缺失的第一个正数。
样例 1
输入:
3 1 2 0
输出:
3
可以尝试原地哈希的思路,利用数组下标作为哈希表的 key。