给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组(-5,3,2,3)中未出现的最小正整数是1;数组{1,2,3)中未出现的最小正整数是4。要求: 给出算法的基本设计思想。

admin2019-08-17  35

问题 给定一个含n(n≥1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组(-5,3,2,3)中未出现的最小正整数是1;数组{1,2,3)中未出现的最小正整数是4。要求:
给出算法的基本设计思想。

选项

答案题目要求算法时间上尽可能高效,因此采用空间换时间的办法。分配一个用于标记的数组B[n],用来记录A中是否出现了1~n中的正整数,B[0]对应正整数1,B[n-1]对应正整数n,初始化B中全部为0。由于A中含有n个整数,因此可能返回的值是1~n+1,当A中n个数恰好为1~n时返回n+1。当数组A中出现了小于等于0或者大于n的值时,会导致1~n中出现空余位置,返回结果必然在1~n中,因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。经过以上分析可以得出算法流程:从A[0]开始遍历A,若0<A[i]<=n,则令B[A[i]-1]=1;否则不做操作。对A遍历结束后,开始遍历数组B,若能查找到第一个满足B[i]==0的下标i,返回i+1即为结果,此时说明A中未出现的最小正整数在1~n之间。若B[i]全部不为0,返回i+1(跳出循环时i=n,i+1等于n+1),此时说明A中未出现的最小正整数是n+1。

解析
转载请注明原文地址:https://jikaoti.com/ti/0MGjFFFM
0

相关试题推荐
最新回复(0)