สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums ซึ่งแสดงถึงตำแหน่งของบ้านบนเส้น 1 มิติ ตอนนี้ให้พิจารณาว่าเรามีไฟถนน 3 ดวงที่เราสามารถติดไว้ที่ใดก็ได้บนเส้น และไฟที่ตำแหน่ง x จะส่องสว่างบ้านทุกหลังในระยะ [x - r, x + r] รวมอยู่ด้วย เราต้องหา r ที่เล็กที่สุดที่จำเป็นในการส่องสว่างบ้านทุกหลัง
ดังนั้นหากอินพุตมีค่าเท่ากับ nums =[4,5,6,7] เอาต์พุตจะเป็น 0.5 เนื่องจากเราสามารถวางหลอดไฟไว้ที่ 4.5, 5.5 และ 6.5 ดังนั้น r =0.5 ดังนั้นไฟสามดวงนี้จึงสามารถส่องสว่างบ้านทั้ง 4 หลังได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน valid() นี่จะใช้เวลา r
-
last_location :=nums[0] + r
-
นับ :=1
-
สำหรับฉันในช่วง 0 ถึงขนาดของ nums ทำ
-
val :=nums[i]
-
ถ้า val - last_location> r แล้ว
-
นับ :=นับ + 1
-
last_location :=val + r
-
-
-
คืนค่า จริง เมื่อนับ <=3 มิฉะนั้น เท็จ
-
จากวิธีหลักให้ทำดังต่อไปนี้ -
-
เรียงเลขรายการ
-
ซ้าย :=0
-
right :=องค์ประกอบสุดท้ายของ nums
-
res :=inf
-
itr :=0
-
ในขณะที่ซ้าย <=ขวาและมัน <20 ทำ
-
กลาง :=ซ้าย +(ขวา - ซ้าย) / 2
-
ถ้า valid(mid) เป็นจริง แล้ว
-
res :=ความละเอียดขั้นต่ำและกลาง
-
ขวา :=กลาง
-
-
มิฉะนั้น
-
ซ้าย :=กลาง
-
itr :=itr + 1
-
-
-
ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution:
def solve(self, nums):
def valid(r):
last_location = nums[0] + r
count = 1
for i in range(len(nums)):
val = nums[i]
if val - last_location > r:
count += 1
last_location = val + r
return count <= 3
nums.sort()
left = 0
right = nums[-1]
res = float("inf")
itr = 0
while left <= right and itr < 20:
mid = left + (right - left) / 2
if valid(mid):
res = min(res, mid)
right = mid
else:
left = mid
itr += 1
return res
ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums)) อินพุต
[4,5,6,7]
ผลลัพธ์
0.5
