Задача: 1287. Element Appearing More Than 25% In Sorted Array
Сложность: easy

Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число.

Пример:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

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

1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num.

2⃣Установите target = arr.length / 4.

3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение.

😎 Решение:

using System.Collections.Generic;

public class Solution {
    public int FindSpecialInteger(int[] arr) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
        int target = arr.Length / 4;
        foreach (int num in arr) {
            if (!counts.ContainsKey(num)) {
                counts[num] = 0;
            }
            counts[num]++;
            if (counts[num] > target) {
                return num;
            }
        }
        return -1;
    }
}

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