请问下述布尔数组分区代码的最坏时间复杂度是否为O(N)？

你的判断完全正确，这段布尔数组分区代码的最坏时间复杂度为O(N)（N为数组元素总数）。

复杂度分析 #

• 核心逻辑采用双指针相向遍历的实现：指针l从数组左端向右移动，指针r从数组右端向左移动，两个指针全程仅向中间移动，不会出现回退
• 所有++l、--r操作的总执行次数最多为N次，每次数组访问、赋值操作均为*O(1)*时间复杂度
• 末尾的数组遍历输出环节同样是O(N)时间复杂度，无更高阶的时间开销，整体最坏时间复杂度稳定为O(N)

代码潜在问题提示 #

你当前的代码存在数组越界风险：两个内层while循环都先执行了指针自增/自减、再做边界判断，当数组全为true或全为false时，指针会先超出数组合法下标范围再触发边界判断，此时已经发生了非法数组访问。可调整条件顺序修复：

// 修复后的内层循环示例
while(l < bA.length-1 && bA[++l] == true) { }
while(0 < r && bA[--r] == false) { }

原代码参考 #

int l = -1;
int r = bA.length;

for ( ; ;) {
    while(bA[++l] == true && l < bA.length-1) { }
    while(bA[--r] == false && 0 < r) { }
    if (l < r) {
        bA[l] = true;
        bA[r] = false;
    } else {
        break;
    }
}

for (int i = 0; i < bA.length; i++) {
    if (i == bA.length - 1) {
        System.out.println(bA[i]);
    } else {
        System.out.print(bA[i]+", ");
    }
}

内容的提问来源于stack exchange，提问作者Cesar A. Saenz