Pythonの等差数列から削除された用語を見つけるプログラム

n-1個の等差数列項を保持するnumsという配列があるとします。 numsの最初または最後の要素を除く1つの要素が以前に削除されました。削除された番号を見つける必要があります。

したがって、入力がnums =[5、7、11、13]の場合、項目は式2i + 5に従うため、出力は9になります。したがって、i=2の場合は2*2+5になります。 =9がありません。

これを解決するには、次の手順に従います-

• numsのサイズが2と同じ場合、

  • （numsに存在するすべての要素の合計）/2のリターンフロア

• nums[0]がnums[1]と同じ場合、/ p>

  • nums [0]

    を返します

• 下：=nums [0]

• アッパー：=numsの最後の要素

• 間隔：=フロア（上-下）/数字のサイズ

• ポインタ：=nums/2のサイズのフロア

• 左：=0

• 右：=numsのサイズ-1

• 左は右と同じではありませんが、実行してください

  • nums[pointer]がnums[0]+インターバル*ポインターと同じでない場合、

    • nums[pointer-1]がnums[0]+ interval *（pointer-1）と同じである場合、

      • nums[0]+間隔*ポインタを返す

    • それ以外の場合

      • 右：=ポインタ

      • ポインタ：=床（左+右）/ 2

  • それ以外の場合

    • 右-左が1と同じ場合、

      • ポインタ：=右

    • それ以外の場合

      • 左：=ポインタ

      • ポインタ：=フロア（左+右）/ 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