Chương trình tìm chỉ mục phần tử xuất hiện nhiều nhất trong mảng ẩn trong Python

Giả sử ta được cho một lớp TestArray chứa mảng private chỉ chứa giá trị 0 hoặc 1; và hai hàm public length() và query(). Hàm length() trả về độ dài mảng, hàm query() trả về ba giá trị khác nhau so sánh các giá trị trong mảng. Hàm nhận bốn giá trị p, q, r, s và hoạt động như sau:

• Nếu cả bốn giá trị tại các chỉ mục đều là 0 hoặc đều là 1: trả về 4.
• Ngược lại nếu ba giá trị giống nhau và giá trị thứ tư khác: trả về 2.
• Ngược lại nếu mảng chứa hai giá trị 0 và hai giá trị 1 tại các chỉ mục: trả về 0.

Ta phải tìm chỉ mục của phần tử xuất hiện nhiều nhất trong mảng không truy cập trực tiếp mảng và chỉ dùng các hàm thành viên của lớp. Nếu số lượng 0 và 1 bằng nhau, trả về -1.

Ví dụ: array = [0, 1, 1, 0, 1, 1, 1, 0], kết quả là 2. Tại chỉ mục 2 giá trị là 1 - giá trị xuất hiện nhiều nhất. Các chỉ mục 1, 4, 5, 6 cũng đúng vì cũng chứa giá trị 1.

Giải thuật

1. n := length()
2. groupA := 1, groupB := 0
3. aIdx := null, bIdx := null
4. first := query(0, 1, 2, 3)
5. second := query(0, 1, 2, 4)
6. For i từ 4 đến n:
   • Nếu query(0, 1, 2, i) == first: groupA++, aIdx := i
   • Ngược lại: groupB++, bIdx := i
7. For i từ 0 đến 2:
   • Tạo danh sách nxt chứa các giá trị 0..4 trừ i
   • Nếu query(nxt) == second: groupA++, aIdx := i
   • Ngược lại: groupB++, bIdx := i
8. Nếu groupA > groupB: trả về aIdx
9. Ngược lại nếu groupB > groupA: trả về bIdx
10. Ngược lại: trả về -1

Ví dụ (Python)

class TestArray:
    def __init__(self, array) -> None:
        self.__arr = array
    
    def length(self):
        return len(self.__arr)
    
    def query(self, p, q, r, s):
        val = self.__arr[p] + self.__arr[q] + self.__arr[r] + self.__arr[s]
        if val == 4 or val == 0:
            return 4
        elif val == 1 or val == 3:
            return 2
        elif val == 2:
            return 0

def solve(reader):
    n, groupA, groupB, aIdx, bIdx = reader.length(), 1, 0, None, None
    first, second = reader.query(0,1,2,3), reader.query(0,1,2,4)
    for i in range(4, n):
        if reader.query(0,1,2,i) == first:
            groupA, aIdx = groupA + 1, i
        else:
            groupB, bIdx = groupB + 1, i
    for i in range(3):
        nxt = [v for v in [0,1,2,3,4] if v != i]
        if reader.query(*nxt) == second:
            groupA, aIdx = groupA + 1, i
        else:
            groupB, bIdx = groupB + 1, i
    return aIdx if groupA > groupB else bIdx if groupB > groupA else -1

arr_ob = TestArray([0, 1, 1, 0, 1, 1, 1, 0])
print(solve(arr_ob))

Input

[0, 1, 1, 0, 1, 1, 1, 0]

Output

2