資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢使列表元素相等所需的最小總成本
假設我們有兩個數字列表，分別稱為 nums 和 costs。現在考慮，有一個操作可以將 nums[i] 增加或減少，成本為 costs[i]。我們可以執行任意數量的此類操作，並且我們希望使 nums 中的所有元素都相等。我們必須找到所需的最小總成本。
因此，如果輸入類似於 nums = [3, 2, 4] costs = [1, 10, 2]，則輸出將為 5，因為我們可以將數字 3 減少到 2，成本為 1。然後我們可以將 4 遞減兩次，每次成本為 2。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 helper()。這將接收目標值。
total := 0
對於每個 i,n 在 enumerate(nums) 中，執行以下操作：
如果目標與 n 不相同，則
total := total + |n-target| * costs[i]
返回 total
從主方法中執行以下操作：
low := 0，high := nums 的最大值
當 low < high 不為零時，執行以下操作：
mid := (low + high) / 2
如果 helper(mid) < helper(mid+1)，則
high := mid
否則，
low := mid + 1
返回 helper(low)
讓我們看看以下實現以更好地理解：
示例
class Solution: def solve(self, nums, costs): def helper(target): total = 0 for i,n in enumerate(nums): if target != n: total += abs(n-target) * costs[i] return total low,high = 0, max(nums) while low < high: mid = low + high >> 1 if helper(mid) < helper (mid+1): high = mid else: low = mid + 1 return helper(low) ob = Solution() nums = [3, 2, 4] costs = [1, 10, 2] print(ob.solve(nums, costs))
輸入
[3, 2, 4], [1, 10, 2]
輸出
5
更新於： 2020-10-07
224 次瀏覽
廣告