У меня просто была проблема с кодообразованием, и я все еще пытаюсь понять, как могут быть выполнены ограничения по пространству и временной сложности.
Проблема заключается в следующем: Доминирующим элементом массива является тот, который занимает более половины позиций в массиве, например:
{3, 67, 23, 67, 67}
67 является доминирующим элементом, потому что он появляется в массиве в 3/5 ( > 50%) положениях.
Теперь вы должны предоставить метод, который принимает массив и возвращает индекс доминирующего элемента, если он существует, и -1, если его нет.
Легко, правда? Хорошо, я мог бы решить проблему удобно, если бы не следующие ограничения:
- Ожидаемая сложность времени - O (n)
- Ожидаемая сложность пространства - O (1)
Я могу видеть, как вы могли бы решить это для O (n) времени с O (n) пространственными сложностями, а также O (n ^ 2) время с O (1) пространственными сложностями, но не с тем, что соответствует как O (n) n) времени и O (1).
Я бы очень хотел увидеть решение этой проблемы. Не волнуйтесь, крайний срок прошел несколько часов назад (у меня было только 30 минут), поэтому я не пытаюсь обмануть. Спасибо.