给定一个含n个整数的数组a,请找到数组中从未出现过的最小正整数
时间: 2023-04-30 13:01:50 浏览: 267
一个未排序的整数数组,请找出其中没有出现的最小的正整数。
5星 · 资源好评率100%
首先,我们可以将数组a中的所有负数和零都去掉,因为它们不可能是最小正整数。
然后,我们可以将数组a中的所有正整数按照从小到大的顺序排序。
接着,我们从1开始遍历这个排序后的数组,如果当前的数不等于遍历到的位置,那么这个数就是从未出现过的最小正整数。
如果遍历完整个数组都没有找到这样的数,那么最小正整数就是数组长度加1。
代码实现如下:
```python
def find_smallest_positive_integer(a):
# 去掉负数和零
a = [x for x in a if x > 0]
# 排序
a.sort()
# 遍历数组
for i, x in enumerate(a):
if x != i + 1:
return i + 1
# 如果遍历完整个数组都没有找到,那么最小正整数就是数组长度加1
return len(a) + 1
```
例如,对于数组a=[3, 4, -1, 1, 2, 5, 7, 0, 8],从未出现过的最小正整数是6,因此调用find_smallest_positive_integer(a)会返回6。
阅读全文