Проблема взята из Элементы программирования Интервью:
Учитывая массив A из n объектов с булевозначными ключами, измените порядок массива так, чтобы объекты, имеющие ключевое ложное значение, отображались первыми. Относительный порядок объектов с ключом true не должен меняться. Используйте O (1) дополнительное пространство и время O (n).
Я сделал следующее: он сохраняет относительный порядок объектов с ключом true и использует O (1) дополнительное пространство, но я считаю, что его временная сложность - O (n * n!).
public static void rearrangeVariant4(Boolean[] a) {
int lastFalseIdx = 0;
for (int i = 0; i < a.length; i++) {
if (a[i].equals(false)) {
int falseIdx = i;
while (falseIdx > lastFalseIdx) {
swap(a, falseIdx, falseIdx-1);
falseIdx--;
}
lastFalseIdx++;
}
}
}
У кого-нибудь есть идея о том, как его решить в O (n) времени?