首页 > 其他分享 >leetcode1004

leetcode1004

时间:2023-05-14 22:22:47浏览次数:28  
标签:二分 leetcode1004 位置 个数 下界 查找

1.二分查找法

用一数组P【i】记录每个位置之前到自己本身位置i有多少个0,只要满足【下界,上界】之间的0个数小于等于k就可以连接成为连续的1。

即P【上界】-P【下界】<=k

因为第一个位置要是为0 要做特殊处理[上界,下界]之间0的个数不能简单用P[上界]-P【下界】,

记有n个元素,从P[0]~P[n+1],

P[0]=0;

P[i]=P[i-1]+(1-nums[i-1))//记录的是第i-1位置对应的0个数,防止在0位置i-1=-1边界溢出

下面讨论二分查找法:

 

标签:二分,leetcode1004,位置,个数,下界,查找
From: https://www.cnblogs.com/wangkaixin-yy/p/17400410.html

相关文章