1차원 선에서 주택의 위치를 나타내는 nums라는 숫자 목록이 있다고 가정합니다. 이제 라인의 아무 곳에나 설치할 수 있는 가로등이 3개 있고 x 위치의 조명이 [x - r, x + r] 범위(포함)의 모든 집에 불을 밝힙니다. 모든 집을 밝히는 데 필요한 가장 작은 r을 찾아야 합니다.
따라서 입력이 nums =[4,5,6,7]과 같으면 출력은 0.5가 됩니다. 램프를 4.5, 5.5 및 6.5에 배치하여 r =0.5가 되도록 할 수 있기 때문입니다. 따라서 이 3개의 조명으로 4개의 집을 모두 밝힐 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
valid() 함수를 정의합니다. 시간이 걸립니다
-
last_location :=nums[0] + r
-
개수 :=1
-
범위 0에서 숫자 크기까지의 i에 대해
-
발 :=숫자[i]
-
val - last_location> r이면
-
개수 :=개수 + 1
-
last_location :=val + r
-
-
-
count <=3이면 true를 반환하고, 그렇지 않으면 false
를 반환합니다. -
주요 방법에서 다음을 수행하십시오 -
-
목록 번호 정렬
-
왼쪽 :=0
-
오른쪽 :=숫자의 마지막 요소
-
res :=inf
-
itr :=0
-
왼쪽 <=오른쪽 및 itr <20인 동안 수행
-
중간 :=왼쪽 +(오른쪽 - 왼쪽) / 2
-
valid(mid)가 참이면
-
res :=res 및 mid의 최소값
-
오른쪽 :=중간
-
-
그렇지 않으면
-
왼쪽 :=중간
-
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