Pythonで最小の絶対和の差を見つけるプログラム

同じサイズの2つの正の値の配列nums1とnums2があるとします。これら2つの配列の絶対和の差は、| nums1 [i] --nums2[i]|の合計です。各0<=i

したがって、入力がnums1 =[2,8,6]、nums2 =[3,4,6]の場合、出力は3になります。これは、2つの可能な最適なソリューションを見つけることができるためです

• インデックス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と同じ場合、

  • return（0）

• minn_diff：=-infinity

• ind：=-1

• 0からnums1-1のサイズのiの場合、実行

  • | nums1 [i] -nums2[i]|の場合> minn_diff、次に

    • ind：=i

    • minn_diff：=| nums1 [i]-nums2 [i] |

• diff：=| nums1 [ind]-nums2 [ind] |

• index：=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と同じ場合、

    • summ：=summ + | nums1 [index]-nums2 [i] |

  • それ以外の場合

    • summ：=summ + | nums1 [i]-nums2 [i] |

• 合計modを返す（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]

出力

3