c语言求几位数给定一个含n(n>1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是。
时间: 2024-05-12 17:16:54 浏览: 109
一个未排序的整数数组,请找出其中没有出现的最小的正整数。
5星 · 资源好评率100%
你好!感谢你使用我开发的ChitGPT进行对话。
针对你的问题,我可以给出如下算法:
1. 首先遍历一遍数组,将所有大于等于1并且小于等于n的数都移到对应的位置上,即将数i放到位置i-1上。如果数组中已经有数i-1了,则不需要移动。
2. 再次遍历数组,找到第一个不在其对应位置上的数,即为未出现的最小正整数。
以下是Python代码实现:
```
def find_missing_num(nums):
n = len(nums)
# 将数i放到位置i-1上
for i in range(n):
while nums[i]>=1 and nums[i]<=n and nums[nums[i]-1]!=nums[i]:
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
# 找到第一个不在其对应位置上的数
for i in range(n):
if nums[i]!=i+1:
return i+1
# 若数组中都出现了1到n,则返回n+1
return n+1
```
希望这个算法能够满足你的需求。如果还有其他问题,请继续问我哦。
阅读全文