Python에서 최소 절대 합계 차이를 찾는 프로그램

<시간/>

크기가 같은 두 개의 양수 값 배열 nums1과 nums2가 있다고 가정합니다. 이 두 배열의 절대 합차는 |nums1[i] - nums2[i]|의 합입니다. 각 0 <=i

따라서 입력이 nums1 =[2,8,6], nums2 =[3,4,6]과 같으면 출력은 3이 됩니다. 두 가지 가능한 최적 솔루션을 찾을 수 있기 때문입니다.

인덱스 1의 요소를 인덱스 0의 요소로 교체:[2,8,6] => [2,2,6] 또는
인덱스 1의 요소를 인덱스 2의 요소로 교체:[2,8,6] => [2,6,6].

둘 다 |2-3|의 합계 차이를 얻습니다. + (|2-4| 또는 |6-4|) + |6-6| =3.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

nums1이 nums2와 같으면
- 리턴(0)
minn_diff :=-무한대
인드 :=-1
범위 0에서 nums1 - 1의 크기에 있는 i에 대해
- 경우 |nums1[i]-nums2[i]|> minn_diff, 다음
  - 인드 :=나는
  - minn_diff :=|nums1[i] - nums2[i]|
diff :=|nums1[ind] - nums2[ind]|
인덱스 :=인드
범위 0에서 nums1 - 1의 크기에 있는 i에 대해
- i가 ind와 같지 않으면
  - if |nums1[i] - nums2[ind]| <차이, 그럼
    - 색인 :=i
    - diff :=|nums1[i]-nums2[ind]|
합계 :=0
범위 0에서 nums1 - 1까지의 i에 대해 수행
- i가 ind와 같으면
  - 합계 :=합계 + |nums1[인덱스] - nums2[i]|
- 그렇지 않으면
  - 합계 :=합계 + |nums1[i] - nums2[i]|
합계 모드 반환(10^9 + 7)

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(nums1, nums2):
   if(nums1==nums2):
      return(0)

   minn_diff = float('-inf')
   ind = -1
   for i in range(len(nums1)):
      if(abs(nums1[i]-nums2[i]) > minn_diff):
         ind = i
         minn_diff = abs(nums1[i]-nums2[i])
   
   diff = abs(nums1[ind]-nums2[ind])
   index = ind
   for i in range(len(nums1)):
      if(i!=ind):
         if(abs(nums1[i]-nums2[ind])<diff):
            index = i
            diff = abs(nums1[i]-nums2[ind])

   summ = 0
   for i in range(len(nums1)):
      if(i==ind):
         summ += abs(nums1[index]-nums2[i])
      else:
         summ += abs(nums1[i]-nums2[i])
   return(summ%(10**9 + 7))

nums1 = [2,8,6]
nums2 = [3,4,6]
print(solve(nums1, nums2))

입력

[2,8,6], [3,4,6]