T41 数组中最小未使用正数
- 使用原地哈希的方法,将每个正整数
x放到索引为x-1的位置上。- 巧妙地利用了数组的索引来建立一个数字与其“理想位置”之间的映射关系。
- 然后遍历数组,找到第一个索引
i使得array[i] != i + 1,则i + 1即为最小未使用正数。 - 如果所有位置都满足
array[i] == i + 1,则最小未使用正数为n + 1。
x 放到索引为 x-1 的位置上。
i 使得 array[i] != i + 1,则 i + 1 即为最小未使用正数。array[i] == i + 1,则最小未使用正数为 n + 1。