给定一个所有值都为1或0的任意数组,有多少个(编辑:长度为N的非重叠窗口的最大数目是多少?窗口必须以1(True)值为中心。(编辑:假设N是奇数)。窗口的两侧可以是0,数组两端的值可以算作有效值。如果可能的话,我更喜欢使用numpy和/或pandas的答案。
真实世界的用例是安排会议,这样它们就不会重叠。该数组可以表示一年中的天数,1表示可用于举行会议的天数,并且有一个规则,即会议必须在两天之间安排。
示例:
array_1 = [1, 0, 0, 1, 0, 0, 1, 0]
array_2 = [0, 0, 0, 1, 1, 1, 0, 0]
count_windows(array=array_1, window_size=3)
out:3解释:按索引显示窗口:[0, 1], [2, 3, 4], [6, 7, 8]
count_windows(array=array_2, window_size=3)
out:1解释:按索引显示窗口:[2, 3, 4]
以索引5为中心的窗口将包括索引4,索引4将与以索引3为中心的窗口重叠
1条答案
按热度按时间bvjxkvbb1#
我有一个很可能是非最优的解决方案(即它不最大化窗口的数量,而是选择第一个有效窗口)。它还有一个嵌套的
for
循环,所以这个解决方案对于大型数组来说会很慢。也许有人可以用这个答案找到一个矢量化的解决方案。本质上,我的解决方案找到值为1的索引(使用
np.where
),然后在每个点周围创建一个索引窗口(我假设window_size
总是奇数)。然后检查每个窗口之间的重叠(使用np.isin
),如果没有重叠,则保留该窗口。最后,它删除可能添加到结果列表中的任何可能的重复行(使用np.unique
),并消除负数(当1接近开始或结束时,会发生负索引)。返回值是一个Python。