algorithm - 在等差数列的 n 个元素的序列中，[n/2] 个元素发生变化。求初始等差级数的差

Question

我有一个大小为 n 的列表，其中包含算术级数的 n 个连续成员，这些成员不按顺序排列。我用一些随机整数更改了此列表中不到一半的元素。从这个新列表中，我如何找到初始算术级数的差异？

我想了很多，但除了暴力之外，我想不出任何其他办法:(

感谢您考虑这个问题:)

Answer 1

一般来说，解决这个问题并不能 100% 确定您的答案是正确的。假设初始列表是以下算术级数(不按顺序排列):

1 3 2 4

随机更改不到一半的元素...例如，我们将 2 更改为 5:

1 3 5 4

如果我们能够首先找出需要更改哪些数字才能获得有效的打乱算术序列，那么我们就可以轻松解决问题中所述的问题。然而，我们可以看到有多种可能的答案，具体取决于我们选择更改的编号:

• 6、3、5、4(相差 1)
• 1、3、2、4(差值为 1)
• 1、3、5、7(相差 2)

无法知道这些可能的序列中哪一个是原始序列，因此您无法确定原始差异是什么。