Часто встречаемый элемент *

Задача. Дан массив целых чисел, которые отсортированы в неубывающем порядке. Необходимо определить есть ли в массиве целое число, которое встречается более 25% случаев. Если такое число есть верните его, в противном случае верните -1.

Примеры:

1. [1, 3, 3, 7, 7, 7, 7, 8, 10]
   Output: 7
2. [1, 1]
   Output: 1

Разбор

Существует несколько способов решения этой задачи, самый очевидный это вариант с использованием хэш-таблицы.

Мы же приведем другое элегантное решение, которое использует тот факт, что массив изначально отсортирован. А также нам известен размер подмассива элементов с одинаковым значением: Length / 4, используем это в решении.

Тогда для того, чтобы определить такой подмассив, нужно лишь проверить его концы и если они совпадают, то мы нашли его. То есть в цикле будем проверять следующее условие: arr[i] == arr[i + Length / 4].

Отдельно стоит упомянуть крайние случаи, если размер массива меньше 3. Тогда мы можем смело вернуть любой из элементов массива.

Смотрите детали реализации ниже.

Реализация

public static int FindFreqNumber(int[] arr) 
{
	int len = arr.Length;
	if (len < 3)
	{
	    return arr[0];
	}

	int size = len / 4;
	for (int i = 0; i < len - size; i++)
	{
	    if (arr[i] == arr[i + size])
	    {
		return arr[i];
	    }
	}

	return -1;
}

https://gist.github.com/unilecs/bd4ae0fc5973b70e3e77e0fcdb3484b7

Play-test

https://dotnetfiddle.net/n98tQ8