algorithm - 从给定的算术级数中查找缺失的数字

Question

我遇到了这个问题，您得到一个数字 N 作为输入，然后是 N 个数字(其中 3<=N<=2500)。这些 N 数字是算术级数(大小为 N+1)的一部分，其中一个数字被删除。所以任务是找到那个丢失的号码。例如

5
1 3 5 9 11  

输出为7

我想出了两种方法，第二种方法通过了所有测试用例，但第一种方法在某些(隐藏)情况下失败。

首先我会解释第二种方法

方法二

Let diff=(last_number-first_number)/N
 //Considering 0 based indexing
 for i=0 to (N-2)
    if( array[i+1] is not equal to (array[i]+diff))
          print (array[i]+diff)
          break

这个方法通过了所有的测试用例。现在我实现的第一个方法，但在某些测试用例中失败了，如下所示

方法一

 //Considering 0 based indexing
 for i=1 to (N-2)
      if (2*array[i] is not equal to (array[i-1]+array[i+1])) then
              if( (array[i]-array[i-1])< (array[i+1]-array[i]))
                      print 2*array[i]-array[i-1]
              else 
                      print 2*array[i]-array[i+1]
              break

谁能解释一下 METHOD I 有什么问题？？我缺少哪些案例。 谢谢。

Answer 1

当数字按降序排列时，方法 1 不起作用。

对于 7 5 1 输出应该是 3 但算法会给出 9。

方法 2 在这种情况下有效，因为差值被正确计算为负数并且算法会相应地进行。