Giả sử chúng ta có một mảng được gọi là nums chứa n-1 số hạng của dãy số học. Một phần tử ngoại trừ phần tử đầu tiên hoặc phần tử cuối cùng của nums đã bị xóa trước đó. Chúng tôi phải tìm số đã bị loại bỏ.
Vì vậy, nếu đầu vào giống như nums =[5, 7, 11, 13], thì đầu ra sẽ là 9 vì, các mục tuân theo công thức 2i + 5, vì vậy đối với i =2, nó sẽ là 2 * 2 + 5 =9 cái còn thiếu.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu kích thước của nums bằng 2, thì
-
tầng trả về của (tổng tất cả các phần tử có trong nums) / 2
-
-
nếu nums [0] giống nums [1] thì / p>
-
trả về số [0]
-
-
thấp hơn:=nums [0]
-
upper:=phần tử cuối cùng của nums
-
khoảng thời gian:=tầng của (trên - dưới) / kích thước của nums
-
con trỏ:=tầng có kích thước là nums / 2
-
trái:=0
-
right:=size of nums - 1
-
trong khi bên trái không giống bên phải, thực hiện
-
nếu nums [con trỏ] không giống với con trỏ nums [0] + khoảng * thì
-
nếu nums [con trỏ - 1] giống với nums [0] + khoảng thời gian * (con trỏ - 1) thì
-
trả về nums [0] + con trỏ khoảng thời gian *
-
-
nếu không,
-
right:=pointer
-
con trỏ:=tầng của (trái + phải) / 2
-
-
-
nếu không,
-
nếu phải - trái bằng 1 thì
-
con trỏ:=right
-
-
nếu không,
-
left:=pointer
-
con trỏ:=tầng của (trái + phải) / 2
-
-
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
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)) Đầu vào
[5, 7, 11, 13]
Đầu ra
9