Số phép toán để làm tất cả phần tử mảng bằng nhau trong Python

Cho mảng các phần tử, cần làm cho tất cả bằng nhau bằng cách tăng 1. Mỗi bước được tăng n - 1 phần tử. Mục tiêu: tính tổng số phép toán cần thiết.

Ví dụ: danh sách [1, 2, 3] cần 3 phép toán. Một giải pháp: mỗi bước tìm số lớn nhất, tăng các phần tử còn lại 1. Xem code:

Ví dụ: phương pháp mô phỏng

def main():
    arr = [1, 2, 3]
    no_of_operations = 0
    flag = 0
    while not are_equal(arr):
        flag = 1
        maximum = max(arr)
        for i in range(len(arr)):
            if arr[i] != maximum:
                arr[i] += 1
        no_of_operations += 1
    print(no_of_operations) if flag == 0 else print(no_of_operations + 1)

def are_equal(arr):
    for i in range(len(arr) - 1):
        if arr[i] != arr[i + 1]:
            return False
    return True

if __name__ == '__main__':
    main()

Kết quả

3

Phương pháp này chậm với mảng lớn. Cách tối ưu: dùng tổng và phần tử nhỏ nhất.

• Tính tổng mảng.
• Tìm phần tử nhỏ nhất.
• Kết quả = tổng - (độ_dài * nhỏ_nhất).

Ví dụ: phương pháp tối ưu

arr = [1, 2, 3]
length = len(arr)
elements_sum = sum(arr)
smallest = min(arr)
print(elements_sum - (length * smallest))

Kết quả

3

Kết luận

Phương pháp 2 đơn giản và nhanh hơn. Thắc mắc hãy bình luận.