[힘 단추] 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% 의 사용 자 를 격파 하 였 습 니 다.

좋은 웹페이지 즐겨찾기