arrays - 在 "out of order"数组中查找数字的最佳方法？

Question

我有一个长度为 10 的数组，其中填充了数字 0-9。

数字(大部分)是按顺序排列的。然而，起始索引处的数字可以是任何数字，并且数字是按升序还是降序排列是未知的(数字一旦达到最小/最大数字就会环绕 - 当达到 9 时为 0，反之亦然)。

这些数字中恰好有一个没有按顺序排列(好像它被拔出并随机插入到数组中)。

例子:

[4, 3, 1, 0, 9, 8, 7, 2, 6, 5]

索引 7 处的数字 2 乱序。索引 1 和 2 之间的数字“差距”是可以的，数字 3 或 1 都不会被视为乱序。

查明乱序号索引的最佳方法是什么？

更多示例-不合适的数字用*标记:

[2, 3, *0, 4, 5, 6, 7, 8, 9, 1]
[5, 6, 7, 9, *8, 0, 1, 2, 3, 4]
[7, 6, 5, 4, 3, *8, 2, 1, 0, 9]
[0, *5, 1, 2, 3, 4, 6, 7, 8, 9]
[4, 3, *0, 2, 1, 9, 8, 7, 6, 5] 

Answer 1

要查找乱序的数字，您需要查看数组中的每个元素。因此，您必须以复杂度 O(n) 遍历整个数组。

当你遍历数组时，你应该

• 计算前一个数与当前数之差的绝对值。
• 计算当前数与下一个数之差的绝对值

如果以上两个差都大于 1 且不等于 n-1(当差为 n-1 时，即您的数组翻转的点)，则该数字是乱序的。