给你一个未排序的整数阵列,请你找出其中没有出现的最小的正整数。
第一种方法,置换,把每个x放到x-1的位置上(减一是因为这里是说正整数,如果不减一会没法处理到0号位置的数)。这样做完之后重新遍历,第一个不等于位置x+1的数就是答案。
21第二种,原地杂凑。杂凑表可以直接处理这个问题,但是需要o(n)的额外空间。我们可以直接原地建立杂凑表。因为答案只可能在(1n+1)的范围内,所以可以原地杂凑。先把所有非正数变为n+1,然后遍历阵列,遇到任何一个小于n+1的数,假如为x,就把x-1的位置的数置为负的。操作完毕后最后遍历阵列,遇到的第一个不是负数的位置x,就返回x+1。如果没有就返回n+1。
需要注意在第二次遍历的时候,判断出数字不是n+1后,应该把阵列先取出来取绝对值,否则会造成访问负数位置,导致越界。