来个算法大佬看下这个题目?

Question

有一个这样的数组

const hourList = [true, true, true, true, true, true, true, true, false,
true, false, false, false, false, false, false, false, false, true,true, true, true, true, true]

如何把 连续 的 true 的下标变成一个二维数组
对应此题就是
[[0,7],[9,9],[18,24]]

要求时间复杂度 O(1)

Answer 1

[true, true, true, true, true, true, true, true, false,
true, false, false, false, false, false, false, false, false, true,true, true, true, true,true].reduce((res,b,i,arr) => {
  var pre = res[res.length-1];
    //为true时判断是否存在上一个区间值，无则push一个区间   
    if(b && (!pre || pre.length == 2)) {
        res.push([i])
    }
    //为false时判断上一个区间是否闭合，无则闭合
  //当遍历到最后一个时判断是否上一个闭合，无则闭合   
  if((!b || i==arr.length-1) && pre?.length==1) {
    // false时下标为当前减1
    pre.push(i + ( b ? 0 : -1 ) )
  }
  return res;
},[])

function rangeOfTrue(list,res=[],i=0) {
  var start = list.indexOf(true,i);
  if(start == -1) return res;
  var end = list.indexOf(false,start);
  if(end == -1) end = list.length;
  res.push([start,end-1]);
  return end == list.length ? res : rangeOfTrue(list,res,end);
}

rangeOfTrue([true, true, true, true, true, true, true, true, false,
true, false, false, false, false, false, false, false, false, true,true, true, true, true, true])

Answer 2

逐个遍历判断

const hourList = [
    true, true, true, true, true, true, true, true, false,
    true, false, false, false, false, false, false, false, false,
    true, true, true, true, true, true
];

const { r: result } = hourList.reduce((result, value, index) => {
    if (!value) {
        result.c = null;
        return result;
    }

    if (!result.c) {
        console.log(value, index);
        result.c = [index, index];
        result.r.push(result.c);
    }
    result.c[1] = index;
    return result;
}, { r: [], c: null });

console.log(result);

查找 index 的方法

因为取最后一个元素要用 result[result.length - 1]，看起来麻烦，所以过程中反了个向，用 unshift 插入数据，当栈用，最后一个元素就是 result[0]。就是最后要 reverse() 增加了点损耗。

let i = 0;
let index;
let target = true;
const result = [];
while ((index = hourList.indexOf(target, i)) >= 0) {
    if ((result[0]?.length ?? 2) === 2) {
        result.unshift([index]);
    } else {
        result[0].push(index - 1);
    }
    target = !target;
    i = index + 1;
}
if (result[0]?.length ?? 2 == 1) {
    result[0].push(hourList.length - 1);
}

console.log(result.reverse());

Answer 3

简单的 O(n) 复杂度实现：

const reduce = (list) => {
    const ans = [];
    for (let i = 0; i < list.length; i++) {
        if (!list[i]) continue;
        if (!i || list[i] !== list[i - 1]) {
            ans.push([i, i]);
        } else ans[ans.length - 1][1] = i;
    }
    return ans;
}