问题来源于 编程面试要素:
给定一个大小为 n 的布尔类型键值对的数组 A,重排数组使得键值为 false 的对象先出现。键值为 true 的对象的相对顺序不应更改。使用 O(1) 的额外空间和 O(n) 的时间。
我做了以下处理,它保留了具有键值 true 的对象的相对顺序,并使用了 O(1) 的额外空间,但我认为它的时间复杂度是 O(n*n!)。
给定一个大小为 n 的布尔类型键值对的数组 A,重排数组使得键值为 false 的对象先出现。键值为 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)时间内解决它吗?