给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组(-5，3，2，3)中未出现的最小正整数是1；数组{1，2，3)中未出现的最小正整数是4。要求：说明你所设计算法的时间复杂度和空间复杂度。

admin2019-08-17 60

问题给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组(-5，3，2，3)中未出现的最小正整数是1；数组{1，2，3)中未出现的最小正整数是4。要求：
说明你所设计算法的时间复杂度和空间复杂度。

选项

答案时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了B[n]，空间复杂度为O(n)。

解析

转载请注明原文地址:https://kaotiyun.com/show/4KCi777K

计算机408

相关试题推荐

随机试题

最新回复(0)