โปรแกรมหาต้นทุนต่ำสุดในการจัดเรียงตัวเลขเป็นลำดับเพิ่มหรือลดใน Python

สมมติว่ามีรายการตัวเลขชื่อ nums เราต้องหาต้นทุนต่ำสุดในการจัดเรียงรายการในลำดับใดลำดับหนึ่ง (เพิ่มหรือลด) ต้นทุนคือผลรวมของความต่างระหว่างค่าเก่าและค่าใหม่ของแต่ละองค์ประกอบ

เช่น ถ้าอินพุตคือ [2, 5, 4] ผลลัพธ์จะเป็น 2

ขั้นตอนการแก้ปัญหา

• temp := คัดลอกอาร์เรย์ nums
• เรียง temp
• c1 := 0, c2 := 0, n := ขนาดของ nums
• for i ในช่วง 0 ถึง n
  • ถ้า nums[i] != temp[i] c1 += |nums[i] - temp[i]|
  • ถ้า nums[i] != temp[n-1-i] c2 += |nums[i] - temp[n-i-1]|
• คืนค่า min(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