algorithm - 查找数组是否是 O(n) 时间和 O(1) 空间中的序列

Question

给定一个可能包含重复的数组，我们如何找到它是否是一个序列？

例如。{7, 3, 5, 4, 6, 2}

是一个序列2, 3, 4, 5, 6, 7

排序是一个明显的解决方案。我们如何在 O(n) 时间和 O(1) 空间内做到这一点？

Answer 1

假设1,2,3,3,4,1是一个有效的未排序序列，2,4,6,8也是一个有效的序列（第二步），但1,3,5,9不是（缺少 7）并假设输入数组可以被覆盖，

1. 确定最大值和最小值：O(n) 时间，O(1) 空间。您可以为此使用数组的第一个和最后一个位置。
2. 确定步骤。这一步是所有乘数中最小的公倍数a_n - min
3. 如果它们相距太远（max - min > (count + 1) * step），则这不能是一个序列。否则，
4. 进行就地整数排序。直到开始 > 结束：
   • 看第一个位置。让价值存在v_0
   • 假设没有重复项 ( (v_0 - min) / step + start) 时的目标位置为i
     • 如果目标位置小于start，则为重复。将其移到后面并减少结束指针
     • 如果目标位置大于end，则序列中缺少某些元素。声称数组不是序列。
   • 如果元素在目标位置，则增加起始指针和min引用
   • 否则，如果目标位置的元素小于参考最小值或等于v_0，则将其交换到数组的末尾并递减结束指针。这是一个副本。
   • 否则将目标位置的元素与v_0.
5. 将数组声明为序列

就地整数排序是 O(n)。在每个步骤中，它要么：

• 缩短输入数组并将所有已排序的元素保持在其目标位置或
• 将一两个先前未排序的元素排序到它们的目标位置。

在排序结束时，每个元素要么是重复块中的副本，要么位于已排序块中的正确位置。

请注意，可以省略第 3 步。#4 将正确确定这不是一个序列，尽管速度较慢。

如果步长必须为 1，则可以稍微简化此算法（请参阅修订版 #1）

Answer 2

该算法（Python）破坏了原始数组，但在其他方面满足 O(n) 时间和 O(1) 额外空间。

# INPUT: An array 'arr' of N integers.
# OUTPUT: If the array consists exactly of the integers
#         S, S+1, ..., S+N-1, for some S, in any order,
#         then modifies 'arr' into a sorted array and returns it.
#         Otherwise, returns False, and 'arr' may have been modified.
def sort_sequence (arr):
    the_min = min(arr)
    the_max = max(arr)
    if the_max - the_min != len(arr) - 1:
        return False
    for i in range(len(arr)):
        arr[i] -= the_min
    for i in range(len(arr)):
        while arr[i] != i:
            j = arr[i]
            t = arr[j]
            if t == j:
                return False
            arr[j] = j
            arr[i] = t
    for i in range(len(arr)):
        arr[i] += the_min
    return arr

我还没有正式证明它有效。

为什么是 O(n)？在最后的双循环中，在一个元素第一次被放入正确的位置后，它只能再被访问一次——要么在另一个内部循环的开始，它被认为在正确的位置，要么在它被发现的地方妨碍重复元素（if t == h部分）。

Answer 3

让我试试：

1. 确定最小值和最大值 – O(n)
2. 制作一个原始数组大小的可空值数组 - O(n)（是的，此处缺少空间要求）
3. 遍历原始数组 (O(n)) 并将找到的数字放在索引 (number - min) 处，如果在那里找到值，则没有序列，如果结束并且没有位置声称，你有一个序列

public bool IsSequence(int[] values)
{
    var min = values[0];
    var max = values[0];
    foreach (var value in values)
    {
        min = min > value ? value : min;
        max = max > value ? max : value;
    }

    if ((max - min + 1) != values.Length)
        return false;

    var testingArray = new int?[values.Length];
    foreach (var value in values)
    {
        var index = value - min;
        if (testingArray[index].HasValue)
            return false;
        else
            testingArray[index] = value;
    }
    return true;
}