Tìm d để tối đa số lượng số 0 trong mảng c[i] = d*a[i] + b[i] trong Python

Giả sử chúng ta có hai mảng A và B chứa n số nguyên. Xét mảng C, trong đó phần tử thứ i là d*A[i] + B[i], với d là một số thực tùy ý. Chúng ta cần tìm giá trị d sao cho mảng C có số lượng số 0 nhiều nhất, đồng thời trả về số lượng số 0 đó.

Ví dụ: nếu A = [15, 40, 45] và B = [4, 5, 6], thì đầu ra sẽ là d = -0.266666, số lượng số 0 là 1.

Giải thuật

Các bước thực hiện:

• Lấy kích thước n của mảng A.
• Tạo một từ điển my_map để đếm tần suất các giá trị d.
• Khởi tạo biến count = 0 cho trường hợp A[i] = 0 và B[i] = 0.
• Duyệt qua từng chỉ số i:
  • Nếu A[i] ≠ 0 và B[i] ≠ 0: tính val = (-1.0 * B[i]) / A[i], tăng đếm của val trong my_map.
  • Nếu A[i] = 0 và B[i] = 0: tăng biến count.
• Tìm tần suất lớn nhất maximum trong my_map.
• Tìm khóa (giá trị d) tương ứng với maximum.
• Kết quả: d tìm được, số lượng số 0 = maximum + count.

Ví dụ (Python)

def find_d_zero(A, B):
    n = len(A)
    my_map = {}
    count = 0
    for i in range(n):
        if B[i] != 0 and A[i] != 0:
            val = (-1.0 * B[i]) / A[i]
            if val not in my_map:
                my_map[val] = 0
            my_map[val] += 1
        elif B[i] == 0 and A[i] == 0:
            count += 1
    maximum = 0
    for item in my_map:
        maximum = max(my_map[item], maximum)
    for keys, values in my_map.items():
        if values == maximum:
            print("d =", keys)
            break
    print("Number of 0s:", maximum + count)

a = [15, 40, 45]
b = [4, 5, 6]
find_d_zero(a, b)

Đầu vào

[15, 40, 45], [4,5,6]

Đầu ra

d = -0.26666666666666666 Number of 0s: 1