สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums ที่มีเงื่อนไขลำดับเลขคณิต n-1 องค์ประกอบหนึ่งยกเว้นองค์ประกอบแรกหรือสุดท้ายของ nums ถูกลบออกก่อน เราต้องหาเบอร์ที่ลบออก
ดังนั้น หากอินพุตเป็น nums =[5, 7, 11, 13] ผลลัพธ์จะเป็น 9 เพราะรายการเป็นไปตามสูตร 2i+5 ดังนั้นสำหรับ i =2 จะเป็น 2*2 + 5 =9 ที่หายไป
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้าขนาดของ nums เท่ากับ 2 แล้ว
-
return floor ของ (ผลรวมขององค์ประกอบทั้งหมดที่มีอยู่ใน nums)/2
-
-
ถ้า nums[0] เหมือนกับ nums[1] แล้ว/p>
-
ส่งคืนหมายเลข[0]
-
-
ต่ำกว่า :=nums[0]
-
upper :=องค์ประกอบสุดท้ายของ nums
-
ช่วงเวลา :=ชั้นของ (บน - ล่าง) / ขนาดของ nums
-
ตัวชี้ :=ชั้นของขนาด nums / 2
-
ซ้าย :=0
-
ขวา :=ขนาดของตัวเลข - 1
-
ในขณะที่ซ้ายไม่เหมือนขวาให้ทำ
-
ถ้า nums[ตัวชี้] ไม่เหมือนกับ 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
