数组中大小为 K 的连续组
Consecutive group with size K in an array
最近在现场面试中被问到这个问题。我仍然想不出解决办法。
问题：
有一个有 N 个插槽的花园。在每个插槽中，有一朵花。 N天后，N朵花将一朵一朵地绽放。每一天，恰好有一朵花开，从那时起就处于盛开状态。
给定一个名为 flowers 的数组，由从 1 到 N 的数字组成。数组中的每个数字代表当天花朵开放的位置。
例如，flowers[i] = x 表示在第 i 天开花的唯一花将在位置 x，其中 i 和 x 将在 1 到 N 的范围内。
给定 K，找到 last 一天，在这一天至少有一组 K 大小的花朵盛开。Return -1 如果没有找到这样的一天
示例：
数组：[3,1,5,4,2]； k = 1
第一天：0 0 1 0 0
第2天：1 0 1 0 0
第三天：1 0 1 0 1
day4 ：1 0 1 1 1 >>> 最后一天可以看到一组大小为k=1
第五天：1 1 1 1 1
答案是第四天（花：1）。
如果 k = 2 或 4
答案是-1.
如果 k = 3
答案是第 4 天（鲜花：3,4,5）。
如果 k = 5
答案是第 5 天（鲜花：1,2,3,4,5）。
编辑 1：
我能够在 O(n^2) 中解决它。但是面试官期望 O(nlogn) 复杂度
对于那些使用 leetcode 的人，这是以下问题的变体：https://leetcode.com/problems/k-empty-slots/description/（只能通过 leetcode 付费订阅访问）
谢谢！！
这个问题可以在 O(nlogn) 中通过实施 Union-Find（使用按等级联合和路径压缩）解决。
最初（在 day=0），每个花槽代表一个不同的集合
大小=0。此时会有N个这样的集合。
变量 k-sets 表示有多少集合的大小恰好为 k。这被初始化为零。变量answer表示最后一次迭代（天）至少有一组大小k；并初始化为 -1;
处理数组（N次迭代）：当花朵盛开时，以下事件发生在插槽index：
- 位置
index 的集合大小现在为 1。如果 k==1 则 k-sets 增加 1
- 右并集（设置在
index+1）：如果你不在位置N（即你不能在边界位置N右并集）然后调用UNION(index, index+1)。仅当 index+1 处的集合大小大于零时才会发生合并。
- Union Left (set at
index-1): 如果不在位置0，则调用UNION(index, index-1)。同样，仅当左集不为空时才会发生并集。
- 如果
k-sets > 0，则 answer = day（即其中 day 是数组的 n-th 迭代）
当合并发生时（称它们为 A 和 B），必须完成三个关于 k-sets 的更新：
- 如果
A的大小是k，那么k-sets--
- 如果
B的大小是k，那么k-sets--
- 若A、B的并集大小为
k，则k-sets++
迭代结束时，print answer
运行时间：有N天，每天的开销与O(logn)呈线性关系，所以运行时间为O(NlogN)
最近在现场面试中被问到这个问题。我仍然想不出解决办法。
问题： 有一个有 N 个插槽的花园。在每个插槽中，有一朵花。 N天后，N朵花将一朵一朵地绽放。每一天，恰好有一朵花开，从那时起就处于盛开状态。
给定一个名为 flowers 的数组，由从 1 到 N 的数字组成。数组中的每个数字代表当天花朵开放的位置。
例如，flowers[i] = x 表示在第 i 天开花的唯一花将在位置 x，其中 i 和 x 将在 1 到 N 的范围内。
给定 K，找到 last 一天，在这一天至少有一组 K 大小的花朵盛开。Return -1 如果没有找到这样的一天
示例：
数组：[3,1,5,4,2]； k = 1
第一天：0 0 1 0 0
第2天：1 0 1 0 0
第三天：1 0 1 0 1
day4 ：1 0 1 1 1 >>> 最后一天可以看到一组大小为k=1
第五天：1 1 1 1 1
答案是第四天（花：1）。
如果 k = 2 或 4
答案是-1.
如果 k = 3
答案是第 4 天（鲜花：3,4,5）。
如果 k = 5
答案是第 5 天（鲜花：1,2,3,4,5）。
编辑 1：
我能够在 O(n^2) 中解决它。但是面试官期望 O(nlogn) 复杂度
对于那些使用 leetcode 的人，这是以下问题的变体：https://leetcode.com/problems/k-empty-slots/description/（只能通过 leetcode 付费订阅访问）
谢谢！！
这个问题可以在 O(nlogn) 中通过实施 Union-Find（使用按等级联合和路径压缩）解决。
最初（在 day=0），每个花槽代表一个不同的集合
大小=0。此时会有N个这样的集合。
变量 k-sets 表示有多少集合的大小恰好为 k。这被初始化为零。变量answer表示最后一次迭代（天）至少有一组大小k；并初始化为 -1;
处理数组（N次迭代）：当花朵盛开时，以下事件发生在插槽index：
- 位置
index的集合大小现在为 1。如果k==1则k-sets增加 1 - 右并集（设置在
index+1）：如果你不在位置N（即你不能在边界位置N右并集）然后调用UNION(index, index+1)。仅当index+1处的集合大小大于零时才会发生合并。 - Union Left (set at
index-1): 如果不在位置0，则调用UNION(index, index-1)。同样，仅当左集不为空时才会发生并集。 - 如果
k-sets> 0，则answer = day（即其中 day 是数组的n-th迭代）
当合并发生时（称它们为 A 和 B），必须完成三个关于 k-sets 的更新：
- 如果
A的大小是k，那么k-sets-- - 如果
B的大小是k，那么k-sets-- - 若A、B的并集大小为
k，则k-sets++
迭代结束时，print answer
运行时间：有N天，每天的开销与O(logn)呈线性关系，所以运行时间为O(NlogN)