如何快速的获取数组中的时间段

stranger
  • 5
新手上路,请多包涵
$arr = [
    [0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1], 
    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0], 
    [0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0]
]

上面每条数据代表每天0-24点,其中包含两个时间段:12:00-次日15:00、12:00-15:00。如何快速的获取其中的时间段

回复
阅读 710
1 个回答

可以做以下优化: 优化前时间复杂度O(24N)优化后O(N),其中N位外层数组长度
思路:用数学函数求出整数的前导零和尾随零的个数然后直接算出他的区间
限制条件:

  1. 一天之内只能有一个,且连续时间段
  2. 得把24位的数组存成一个unsigned的32位整数

下面是javascript参考代码

var clz = Math.clz32;
function ctrz(integer){ // 计算尾随0个数
    // 1. 将第一个1之后的高数位全部置为1
    // 00000000000000001000000000001000 => 11111111111111111111111111111000
    integer |= integer << 16;
    integer |= integer << 8;
    integer |= integer << 4;
    integer |= integer << 2;
    integer |= integer << 1;
    // 2. 然后,对该数取反,此时低位的1的个数即为所求
    return 32 - clz(~integer) |0; // `|0`用于保证结果为整数
}

const date = [
0b000000000001111111111111,
0b111111111111111000000000, 
0b000000000001111000000000
]

const getDateSegements = (arr) => {
  return arr.map((v) => {
    const s = clz(v) - 8;
    const e = 23 - ctrz(v);

    return s + "-" + e;
  });
};

getDateSegements(date) //["11-23", "0-14", "11-14"]
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏