Задача: 1538. Guess the Majority in a Hidden Array
Сложность: medium

У нас есть целочисленный массив nums, где все числа в nums равны 0 или 1. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:

int query(int a, int b, int c, int d): где 0 <= a < b < c < d < ArrayReader.length(). Функция возвращает распределение значений 4 элементов и возвращает:
4: если значения всех 4 элементов одинаковы (0 или 1).
2: если три элемента имеют значение 0 и один элемент имеет значение 1 или наоборот.
0: если два элемента имеют значение 0 и два элемента имеют значение 1.

int length(): Возвращает размер массива.

Вам разрешено вызывать query() не более 2 * n раз, где n равно ArrayReader.length().

Верните любой индекс самого частого значения в nums, в случае ничьей верните -1.

Пример:

Input: nums = [0,0,1,0,1,1,1,1]
Output: 5
Explanation: The following calls to the API
reader.length() // returns 8 because there are 8 elements in the hidden array.
reader.query(0,1,2,3) // returns 2 this is a query that compares the elements nums[0], nums[1], nums[2], nums[3]
// Three elements have a value equal to 0 and one element has value equal to 1 or viceversa.
reader.query(4,5,6,7) // returns 4 because nums[4], nums[5], nums[6], nums[7] have the same value.
we can infer that the most frequent value is found in the last 4 elements.
Index 2, 4, 6, 7 is also a correct answer.

👨‍💻 Алгоритм:

1⃣Получите n вызовом функции length. Объявите и инициализируйте переменные cntEqual = 1, cntDiffer = 0, indexDiffer = -1. Вызовите query(0, 1, 2, 3) и сохраните результат в переменной query0123. Вызовите query(1, 2, 3, 4) и сохраните результат в переменной query1234. Если query1234 равно query0123, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 4.

2⃣Итерация от i = 5 до n-1. Если значение query(1, 2, 3, i) равно query0123, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = i. Дополнительные проверки для первых элементов: если query(0, 2, 3, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 1. Если query(0, 1, 3, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 2. Если query(0, 1, 2, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 3.

3⃣Если cntEqual > cntDiffer, верните 0. Если cntDiffer > cntEqual, верните indexDiffer. Верните -1.

😎 Решение:

class Solution:
    def __init__(self):
        self.cntEqual = 1
        self.cntDiffer = 0
        self.indexDiffer = -1

    def f(self, equal, i):
        if equal:
            self.cntEqual += 1
        else:
            self.cntDiffer += 1
            self.indexDiffer = i

    def guessMajority(self, reader: 'ArrayReader') -> int:
        n = reader.length()
        query0123 = reader.query(0, 1, 2, 3)
        query1234 = reader.query(1, 2, 3, 4)
        self.f(query1234 == query0123, 4)
        for i in range(5, n):
            self.f(reader.query(1, 2, 3, i) == query0123, i)
        self.f(reader.query(0, 2, 3, 4) == query1234, 1)
        self.f(reader.query(0, 1, 3, 4) == query1234, 2)
        self.f(reader.query(0, 1, 2, 4) == query1234, 3)
        return 0 if self.cntEqual > self.cntDiffer else self.indexDiffer if self.cntDiffer > self.cntEqual else -1

Ставь 👍 и забирай 📚 Базу знаний