检查随机数列表是否包含 1 到 n 范围的有效方法

Question

如果我有一个随机打乱的数组，其中包含数字 1 到 n，那么找到该数组包含范围 1 到 n（无重复）的好方法是什么？例如，

n = 6; [1, 3, 6, 2, 4, 5] => true
n = 6; [1, 1, 2, 4, 5, 6] => false

Answer 1

听起来像家庭作业，但是......

使用 Set 非常简单：

/* Convert to your favorite language */

validateArray(a, n) {
  assertEqual(n, a.length)
  def s = new Set(a); // set with all elements of a
  assertEqual(s, Set(1..n)); // should be equal to set containing 1 to n
}

Answer 2

创建一个大小为 n 的数组，遍历数组并以此作为索引递增数组中的位置。如果任何时候 counts 数组具有非 0 或非 1 值，您可以停止。如果找不到索引，您可以立即停止，因为您知道自己没有它。

这是一个简单的 Java 示例。在此示例中，您不需要在最后进行计数，因为任何会导致非 1 值的情况都会在中间导致失败。

boolean isRange(int[] arr) {

    int[] counts = new int[arr.length];

    for(int i : arr) {
        if(i < 1 || i > arr.length) return false;
        if(counts[i - 1] != 0) return false;
        counts[i-1] = 1;
    }
    return true; // if it wasn't, we would have failed by now

}

Answer 3

使用高斯公式预先计算最终总和：

final_sum = k * (k+1)
            ---------
                2

对已打乱的列表进行线性循环，将数字相加，如果运行总和与最终总和相同，则返回 true。

Answer 4

您需要对数组进行排序。以下是一些流行选择的链接，http://en.wikipedia.org/wiki/Sorting_algorithm。就我个人而言，我建议冒泡排序作为简单的解决方案，并推荐合并排序作为更难、更快的版本。

列表排序后，您可以通过迭代数组并确保下一个 # 大于前一个来检查重复。此外，还可以将其添加到排序中以缩短计算时间。

最后，检查第一个和最后一个数字，确保它们等于 1 和 n。

Answer 5

如果不允许有额外的空间（面试问题中的典型约束），那么您可以先对数组进行排序，然后从左到右顺序扫描排序后的数组，看看每个元素是否都比前一个元素大1。时间复杂度为O(n*logn)。