给定N个整数数组A的Python返回在O(n)时间复杂度中A中不出现的最小正整数(大于0)
给定N个整数数组A的Python返回在O(n)时间复杂度中A中不出现的最小正整数(大于0)
提问于 2018-03-11 19:15:44
例如：
输入:a=6 4 3 -5 0 2 -7 1输出:5
因为5是数组中没有出现的最小正整数。
我已经为这个问题写了两个解决方案。第一个很好，但我不想使用任何外部库+它的O(n)*log(n)复杂性。第二个解决方案“我需要您的帮助来优化它”，当输入是混沌序列length=10005 (带有负)时，会出现一个错误。
解决方案1：
from itertools import count, filterfalse
def minpositive(a):
return(next(filterfalse(set(a).__contains__, count(1))))解决方案2：
def minpositive(a):
count = 0
b = list(set([i for i in a if i>0]))
if min(b, default = 0) > 1 or min(b, default = 0) == 0 :
min_val = 1
else:
min_val = min([b[i-1]+1 for i, x in enumerate(b) if x - b[i - 1] >1], default=b[-1]+1)
return min_val注:这是一个演示测试，方案1得到100%，解决方案2得到77 %。 "solution2“中出现错误的原因是： 性能测试->介质混沌序列length=10005 (含负)得到3预期10000 性能测试->大型混沌+多-1，1，2，3(含负)得到5预期10000。
回答 18
Stack Overflow用户
回答已采纳
发布于 2018-03-11 22:23:33
在Python中测试一个数字是否存在是非常快速的，因此您可以尝试如下所示：
def minpositive(a):
A = set(a)
ans = 1
while ans in A:
ans += 1
return ansStack Overflow用户
发布于 2021-02-10 22:37:46
对于大型数组来说非常快。
def minpositive(arr):
if 1 not in arr: # protection from error if ( max(arr) < 0 )
return 1
else:
maxArr = max(arr) # find max element in 'arr'
c1 = set(range(2, maxArr+2)) # create array from 2 to max
c2 = c1 - set(arr) # find all positive elements outside the array
return min(c2)Stack Overflow用户
发布于 2022-07-12 22:58:11
我有个简单的解决办法。不需要分类。
def solution(A):
s = set(A)
m = max(A) + 2
for N in range(1, m):
if N not in s:
return N
return 1注:这是100%的总分(正确和性能)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/49224022
复制相关文章
相似问题
腾讯云开发者
