Kiểm tra có thể làm hai mảng bằng nhau bằng cách sửa một phần tử trong Python

Cho hai mảng nums1, nums2 và một giá trị k. Ta có thể thay đổi đúng một phần tử của nums1 bằng cách cộng thêm một giá trị bất kỳ trong đoạn [-k, k]. Kiểm tra xem có thể làm cho hai mảng giống hệt nhau không.

Ví dụ: nums1 = [5,7,11], nums2 = [5,5,11], k = 8 → có thể cộng -2 vào nums1[1] để được 5 → trả về True.

Giải thuật

• Sắp xếp cả hai mảng.
• Tìm chỉ số idx nơi hai mảng khác nhau (chỉ cho phép tối đa một vị trí khác nhau).
• Nếu không có vị trí khác nào (idx == -1) hoặc độ chênh tuyệt đối tại vị trí đó ≤ k thì trả về True.

Mã ví dụ

def solve(nums1, nums2, k):
    nums1.sort()
    nums2.sort()
    temp = False
    idx = -1
    for i in range(len(nums1)):
        if nums1[i] != nums2[i]:
            if temp:
                return False
            temp = True
            idx = i
    if idx == -1 or abs(nums1[idx] - nums2[idx]) <= k:
        return True
    return False

nums1 = [5,7,11]
nums2 = [5,5,11]
k = 8
print(solve(nums1, nums2, k))

Đầu vào

[5,7,11], [5,5,11], 8

Đầu ra

True