时间戳

首页 > 解决方案 > 返回最小正整数 > 0

algorithm - 返回最小正整数 > 0

问题描述

参考以下问题：

That, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

1 Given A = [1, 2, 3], the function should return 4. 

2 Given A = [−1, −3], the function should return 1.

在给定1= 为什么它期望返回 4。他们是如何得出 4 的？

并给出2= 为什么它期望返回 1。他们是如何得出 1 的？

当问题说明 o 得到大于 0 的正整数时，(integer> 0)其中that does not occur in A.是不明确的（我假设它需要一个唯一的值在里面A？。

我错过了什么？

PS：我没看懂标题MISSING INTEGER

标签： algorithmtime-complexity

解决方案

一种解决方案是选择输入数组的最小正值，然后检查下一个正整数是否也存在于输入数组中。如果不是，则返回它，如果存在，则检查下一个整数是否存在，依此类推。

此外，时间复杂度在最坏的情况O(n log(n))下n是输入数组的大小，因为您永远不必将初始猜测增加超过n（一行中不能有多个n整数），并且排序是 O(n log(n)).

一些伪代码可能如下所示：

int findSmallestInt(int[] array) {

  // sort input array

  // check if no positive elements
  if (array[array.size - 1] < 0) {
    return 1;
  }

  int smallestInt = array[0];

  // make sure smallestInt is positive
  for (int i = 0; i < array.size && smallestInt < 0; i++) {
    smallestInt = array[i];
  }

  for (int i = 0; i < array.size; i++) {
    smallestInt += 1;
    if (!array.contains(smallestInt)) {
      return smallestInt;
    }
  }

}

另外，回答你上面的两个问题：

在 1 中它返回 4，因为它是 A 中不存在的最小正整数，在 2 中它返回 1，因为它是 A 中不存在的最小非零正整数。

推荐阅读