Python程式：查詢等差數列中移除的項

假設我們有一個名為nums的陣列，其中包含n-1個等差數列項。在移除一個元素（除了第一個或最後一個元素）之前。我們需要找到被移除的數字。

因此，如果輸入類似於nums = [5, 7, 11, 13]，則輸出將為9，因為這些項遵循公式2i+5，所以對於i = 2，它將是2*2 + 5 = 9，這是缺失的。

為了解決這個問題，我們將遵循以下步驟：

  • 如果nums的大小為2，則

    • 返回nums中所有元素之和的向下取整/2

  • 如果nums[0]等於nums[1]，則

    • 返回nums[0]

  • lower := nums[0]

  • upper := nums的最後一個元素

  • interval := 向下取整(upper - lower) / nums的大小

  • pointer := 向下取整nums的大小 / 2

  • left := 0

  • right := nums的大小 - 1

  • 當left不等於right時，執行以下操作：

    • 如果nums[pointer]不等於nums[0] + interval * pointer，則

      • 如果nums[pointer - 1]等於nums[0] + interval *(pointer - 1)，則

        • 返回nums[0] + interval * pointer

      • 否則，

        • right := pointer

        • pointer :=向下取整(left + right) / 2

    • 否則，

      • 如果right - left等於1，則

        • pointer := right

      • 否則，

        • left := pointer

        • pointer := 向下取整(left + right) / 2

示例

讓我們看看下面的實現來更好地理解

def solve(nums):
   if len(nums) == 2:
      return sum(nums) // 2

   if nums[0] == nums[1]:
      return nums[0]

   lower = nums[0]
   upper = nums[-1]
   interval = (upper - lower) // len(nums)

   pointer = len(nums) // 2

   left = 0
   right = len(nums) - 1

   while left != right:
      if nums[pointer] != nums[0] + interval * pointer:
         if nums[pointer - 1] == nums[0] + interval * (pointer -1):
            return nums[0] + interval * pointer
         else:
            right = pointer
            pointer = (left + right) // 2
      else:
         if right - left == 1:
            pointer = right
         else:
            left = pointer
            pointer = (left + right) // 2

nums = [5, 7, 11, 13]
print(solve(nums))

輸入

[5, 7, 11, 13]

輸出

9

更新於：2021年10月11日

155 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告