Python程序：查找将数字按升序或降序排列的最小成本

假设我们有一个名为 nums 的数字列表，我们需要找到将列表按任意顺序（升序或降序）排序的最小成本。这里的成本是任何元素的旧值和新值之间的差之和。

因此，如果输入类似于 [2, 5, 4]，则输出将为 2。

为了解决这个问题，我们将遵循以下步骤：

• temp:= 复制数组 nums
• 对列表 temp 进行排序
• c1:= 0, c2:= 0
• n:= nums 的大小
• 对于范围从 0 到 n 的 i，执行以下操作：
  • 如果 nums[i] 与 temp[i] 不相同，则
    • c1 := c1 + |nums[i]-temp[i]|
  • 如果 nums[i] 与 temp[n-1-i] 不相同，则
    • c2 := c2 + |nums[i]-temp[n-i-1]|
• 返回 c1 和 c2 的最小值

让我们看看下面的实现以更好地理解：

示例

class Solution:
   def solve(self, nums):
      temp=nums.copy()
      temp.sort()
      c1=0
      c2=0
      n=len(nums)
      for i in range(n):
         if nums[i]!=temp[i]:
            c1+=abs(nums[i]-temp[i])
         if nums[i]!=temp[n-1-i]:
            c2+=abs(nums[i]-temp[n-i-1])
      return min(c1,c2)
ob = Solution()
print(ob.solve([2, 5, 4]))

输入

[2, 5, 4]

输出

2

Arnab Chakraborty

更新于: 2020年10月6日

721 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习