หาตัวเลขที่ซ้ำมากที่สุดในเวลา O(n) และพื้นที่ O(1) ใน Python

สมมติว่าเรามีอาร์เรย์ขนาด n โดยสมาชิกอยู่ในช่วง 0 ถึง k-1 (k เป็นจำนวนเต็มบวก, k ≤ n) หาตัวเลขที่ซ้ำมากที่สุด

เช่น k = 8, A = [3, 4, 4, 6, 4, 5, 2, 8] ผลลัพธ์คือ 4

ขั้นตอนการแก้ปัญหา (Technique: ใช้ค่าอาร์เรย์เป็นดัชนี)

1. วนลูป i จาก 0 ถึง n-1: เพิ่ม k เข้าไปที่ A[A[i] % k]
2. หลังจบลูป ค่าที่มากที่สุดในอาร์เรย์จะสอดคล้องกับตัวเลขที่ซ้ำมากที่สุด
3. คืนค่าดัชนีของค่าสูงสุด

ตัวอย่างโค้ด Python

def get_max_repeating(A, k):
    n = len(A)
    for i in range(n):
        A[A[i] % k] += k
    max_val = A[0]
    result = 0
    for i in range(1, n):
        if A[i] > max_val:
            max_val = A[i]
            result = i
    return result

A = [3, 4, 4, 6, 4, 5, 2, 8]
k = 8
print(get_max_repeating(A, k))

อินพุต

[3, 4, 4, 6, 4, 5, 2, 8], 8

เอาต์พุต

4