查找数组是否为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,则将其交换到数组的末尾并递减结束指针.这是重复的.
   • else用目标位置交换元素v_0.
5. 声明数组序列

就地整数排序是O(n).在每一步中它都是:

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

在排序结束时,每个元素在重复块中都是重复的,或者在排序块中的正确位置.

注意,可以省略步骤#3.#4将正确地确定这不是一个序列,虽然速度较慢.

如果步骤必须为1,则可以稍微简化该算法(参见修订版#1)

Answer 2

让我尝试一下：

1. 确定最小值和最大值 – O(n)
2. 创建一个原始数组大小的可为空值的数组 - O(n)（是的，这里缺少空间要求）
3. 迭代原始数组（O（n））并将找到的数字放在索引（数字-分钟）处，如果在那里找到一个值，则没有序列，如果到达终点并且没有位置声称，你有一个序列

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;
}