找出数组中不出现的最小正整数

Question

我正在尝试以下练习来提高我的在线技能，我遇到了以下问题。

This is a demo task.

Write a function: class Solution { public int solution(int[] A); } 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. Given A = [1, 2, 3], the function should return 4. Given A = [-1, -3], the function should return 1.

Write an efficient algorithm for the following assumptions: • N is an integer within the range [1..100,000); • each element of array A is an integer within the range (-1,000,000.. 1,000,000).

我使用以下解决方案解决了它：

<?php

class Solution {
    public function($A) {
        $posInts = [1, 2, 3, 4, 5, 6, 7, 8, 9];
        $diffs = array_diff($postInts, $A);
        $smallestPosInt = min($diffs);
        return $smallestPosInt;
    }
}

但是在提交后我得到了以下分数：

现在我很不确定我在这里做错了什么或者我如何用更好的算法重写代码。

Answer 1

我会循环（递增）任何可能的整数：

function solution($A) {
    $result = 1;
    $maxNumber = max($A);
    for (; $result <= $maxNumber; $result++) {
        if (!in_array($result, $A)) {
            break;
        }
    }
    return $result;
}

var_dump(solution([1, 3, 6, 4, 1, 2])); // int(5)
var_dump(solution([1, 2, 3])); // int(4)
var_dump(solution([-1, -3])); // int(1)

// As a bonus, this also works for larger numbers:
var_dump(solution([1, 3, 6, 4, 1, 2, 7, 8, 9, 10, 11, 12, 13, 5, 15])); // int(14)

关于性能的编辑：

正如评论中所指出的（您自己也说过），这不是一个非常有效的解决方案。

虽然我目前没有足够的时间进行真正的性能测试，但我认为这应该接近 O(n) 解决方案：（请记住，我不确定数组是如何在PHP)

的C端

function solution($A) {
    $result = 1;
    $maxNumber = max($A);
    $values = array_flip($A);
    for (; $result <= $maxNumber; $result++) {
        if (!isset($values[$result])) {
            break;
        }
    }
    return $result;
}
// Not posting the output again because it is naturally the same ;)

这里的“技巧”是先翻转数组，使值成为索引。因为 a) 我们不关心原始索引并且 b) 我们不关心重复值是否相互覆盖，所以我们可以安全地这样做。

使用 isset() 而不是 in_array() 应该快很多，因为它基本上只是检查变量（在这种情况下存储在特定索引处数组的）存在并且 PHP 因此不必遍历数组以检查我们循环的每个数字是否存在于其中。

P.S.: 仔细想想我认为这可能仍然更接近 O(n*2) 因为 max() 可能会循环寻找最高值。您也可以删除该行，并只检查 PHP 中的最高数字作为紧急出口，例如： for (; $result <= PHP_INT_MAX; $result++) { ... } 作为进一步优化。或者可能只是硬编码任务中指定的最高允许数量。

Answer 2

如果允许我们修改输入，就地执行此操作，否则创建一个大小为 n + 1 的新数组：

对于原数组中遇到的每个元素，如果大于n+1或小于1，则在该元素的索引处赋值0（如果原地执行则为索引-1）；否则在数组的索引处分配 1，如果不同，则在其自己的索引处分配 0。之后运行第二次遍历并报告第一个索引（索引 + 1，如果执行到位）大于零，值为 0，或 n + 1。

[1, 3, 6, 4, 1, 2]

=>

[1, 1, 1, 1, 0, 1]

report 5

Answer 3

使用 Javascript 以尽可能最佳的方式检查这个答案 - 如果我没记错的话 - O(N).

function solution(A) {
  const set = new Set(A)
  let i = 1

  while (set.has(i)) {
    i++
  }
  return i
}

找出数组中不出现的最小正整数

Find the smallest positive integer that does not occur in an array

php

algorithm

data-structures