[힘 단추] 1300: 배열 을 바 꾼 후 목표치 에 가장 가 까 운 배열 과
10864 단어 다이 어 리
정수 배열 arr 와 목표 값 target 을 드 립 니 다. 정수 value 를 되 돌려 주 십시오. 배열 의 모든 value 이상 의 값 을 value 로 바 꾼 후에 배열 의 값 과 가장 가 까 운 target (이들 의 차 이 를 나타 내 는 절대 값 이 가장 작 습 니 다).
target 에 가장 가 까 운 방안 이 여러 가지 있다 면 이 정수 들 의 최소 값 을 되 돌려 주 십시오.
답 이 꼭 arr 의 숫자 는 아니 니 주의 하 세 요.
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
알고리즘 사고
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
arr.sort()
return self.hel(arr,target)
def hel(self,arr,target):
n=len(arr)
z=target/n
if z==arr[0]:return arr[0]
elif z<arr[0]:
if z-int(z)>0.5:
return int(z)+1
else:
return int(z)
elif z>arr[0]:
i=0
while z>arr[i]:
target-=arr[i]
n-=1
if n==0:return arr[-1]
z=target/n
i+=1
# if n==1:return arr[-1]
return self.hel(arr[i:],target)
실행 시: 44ms, 모든 Python 3 제출 에서 98.92% 의 사용자 메모리 소모: 15MB, 모든 Python 3 제출 에서 25.00% 의 사용 자 를 격파 하 였 습 니 다.
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
arr.sort()
self.arr=arr
return self.hel(0,len(arr),target)
def hel(self,i,n,target):
z=target/n
if z==self.arr[i]:return self.arr[i]
elif z<self.arr[i]:
if z-int(z)>0.5:
return int(z)+1
else:
return int(z)
elif z>self.arr[i]:
while z>self.arr[i]:
target-=self.arr[i]
n-=1
if n==0:return self.arr[-1]
z=target/n
i+=1
# if n==1:return arr[-1]
return self.hel(i,n,target)
실행 시: 40 ms, 모든 Python 3 제출 에서 99.46% 의 사용자 메모리 소모: 14.8 MB, 모든 Python 3 제출 에서 25.00% 의 사용 자 를 격파 하 였 습 니 다.