测试一系列数字以确保它们符合序列 1,2,3...n

Question

我正在尝试找到一个稍微更优雅的解决方案来查找数字序列是否有序。这是一个网络表单，我让用户有机会对项目进行编号并设置订单。我知道最大项目数，并且应该始终从 1 开始。

现在（我知道这是不正确的）我测试以确保所有数字都不同并且加起来达到应有的值（例如，对于我测试的三个项目，它加起来为 6）。有谁有更好/更准确的（因为有可能破坏我的）解决方案？我正在使用 php，但我真正想要的是逻辑，因此您的示例可以是伪代码或任何相对易于阅读的语言。

Answer 1

只需对用户输入的数字进行排序，然后查看它们是否与您递增 1 的索引匹配。

nMax = 10
sortedUserArray = Sort(UserArray)

For i = 1 To nMax
    If Not sortedUserArray(i) = i Then
        ' Input not valid. 
        ' Throw an error or something. 
    End If
Next i

对于 Sort 部分，存在多种排序算法：快速排序，直接插入< /a>,Heapsort 等。只需选择一个适合您的需求并进行搜索即可找到现成的过程网络。您选择的语言甚至可能有一些内置的排序算法，因此您甚至可能不需要看那么远。

Answer 2

由于您知道最大项目数，因此您可以通过简单地分配布尔数组并填充它来避免排序。在伪代码中：

define numsInOneThruN (int xarr[], int sz):
    # Declare the boolean array and initialise to all false.

    declare isSet[1..sz]
    for all i in 1..sz:
        isSet[i] = false

    # For every number in list, if within range, set boolean value to true.

    for all i in xarr:
        if i >= 1 and i <= sz:
            isSet[i] = true

    # Check that all boolean values are true.

    for all i in 1..sz:
        if not isSet[i]:
            return false

    return true

这具有 O(n) 时间复杂度的优点，而不是最好情况的 O(n log n) - 这可能并不重要对于小型数据集，但对于较大的数据集可能会变得很重要。

您还应该考虑到这样的事实：这比就地排序具有更高的空间复杂度，因为它使用等于输入大小的数组。这使得排序选项的空间复杂度为 O(n)，而不是 O(1)。

与往常一样，您通常可以根据需要权衡空间与时间。

Answer 3

如果您已经确定这些数字都不同，则只需检查最小值和最大值。只有 n 个不同的数满足 1 <= x <= n。