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

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

admin2019-08-17  39
问题 给定一个含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://kaotiyun.com/show/pKCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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