Как мы можем оптимизировать этот алгоритм с O(N ** 2) до большей сложности, чтобы пройти тест производительности? ⇐ JAVA

[Anonymous]

Цель решения — вычислить количество пар нулей и единиц без избыточности.
Предположим, индекс 0 имеет значение 0 и индекс 1< /code> имеет значение 1, что означает, что ввод выглядит так: [0, 1]
И это просто означает, что теперь у нас есть 1 пара и результат должны быть 1
Другой пример: при вводе [0, 1] теоретически у нас должно быть 2 пары [0, 1] и [1, 0], которые считаются избыточными, и он должен выбрать только один из них, поэтому результат здесь должен быть 1
Другой пример: при вводе [1, 0] пары должны начинаться только с индексов нулей, а не единиц, что означает, что [0, 1] является успешной парой но [1, 0] нет, и результат в этом случае должен быть 0
И если результат превышает 1000000000, то так и должно быть return -1
В настоящее время у меня есть решение, которое обеспечивает 100% правильность, но с точки зрения производительности оно фактически терпит неудачу.
Сложность это решение O(N ** 2)
Решение следующее:

Код: Выделить всё

        int result = 0;
int len = a.length;

for (int i = 0; i < len; i++) {
int current = a[i];

if (current != 0) {
continue;
}

for (int inner = i; inner < len; inner++) {
if (current != a[inner]) {
result++;
}
}
}

return (result > 1000000000) ? -1 : result;

Чего я хочу добиться, так это представить решение меньшей сложности, чтобы пройти тесты производительности. Можем ли мы сделать что-то лучше?
Вот несколько тестовых примеров:

Код: Выделить всё

[0, 1, 0, 1, 1]

ожидаемый результат — 5, то есть [0, 1], [0, 3], [0, 4], [2, 3], [2, 4]

Код: Выделить всё

[0, 1, 1, 1, 1]

ожидаемый результат — 4, то есть [0, 1], [0, 2], [0, 3], [0, 4]
< р>

Код: Выделить всё

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

ожидаемый результат — 8, то есть [0, 1], [0, 4], [0, 6], [2, 4], [2, 6], [3, 4], [3, 6], [5, 6]
Входные выборки должны представлять собой один массив из 0 или 1
Но если количество входных данных превышает 10 000 записей, тест производительности не может быть выполнен в течение определенного периода времени, например: 0,6 секунды.

Подробнее здесь: https://stackoverflow.com/questions/791 ... y-in-order