查找'shortest range of indices'的大小，其中查找所有唯一路径被传递

给定一个字符串数组，查找查找所有唯一路径的">最短索引范围"的大小被传递。

例如，A = { E, R, E, R, A, R, T, A }，它应该是5。如我们所见，A[2] = E and A[6] = T范围包含所有唯一路径。(在本例中为 E、R、A、T)

我可以用如下所示的多个循环来解决。(由 Kotlin 解决。

fun problem(array: Array<String>): Int {
if (array.isEmpty()) return 0
val unique = array.distinct()
var result = 200000
for (i in 0 until A.size) {
val tempSet = HashSet<String>()
val remaining = A.sliceArray(i until array.size)
var count = 0
while (true) {
tempSet.add(remaining[count])
if (unique.size == tempSet.size) break
count++
if (count == remaining.size) {
count = 200000
break
}
}
result = Math.min(result, count + 1)
}
return result
}

但是当一个大数组(大约 100,000 个)进来时，我不知道如何减少时间。我该怎么办？

一些测试用例：

[E， R，

E， R， A， R， T， A] -> 5.因为 [2..6] 包含所有唯一路径。(E， R， A， T)
A， R] -> 3.因为 [3..5] 包含所有唯一路径。(丙、甲、右)
E， R] -> 6.因为 [1..6] 包含所有唯一路径。(T， A， R， E)
R， C， T， E， A， R] -> 5.因为 [2..6] 包含所有唯一路径。(R， C， T， E， A)

这个问题可以通过"两点"方法有效解决。

使字典结构包含 char 作为键和计数器作为值(在最简单的情况下 - int 数组)

在 0 中设置两个索引 L 和 R。

向右移动 R，用于相应字典元素的当前字符增量计数器。当字典大小(在数组 - 非零元素数的情况下)等于unique时，停止

现在向右移动L，对于相应dict元素的当前字符递减计数器，当计数器变为零时删除元素。当字典大小小于unique时，停止。在最后一步L..R 间隔包含所有可能的项目。

继续使用 R 等等

选择扫描期间的最短间隔。

此处为类似问题提供 Python 代码

短语"所有唯一路径"我将解释为"所有可能的值"。

对于具有k唯一值的长度n字符串，这可以及时解决，O(n log(k))使用字典和优先级队列。关键思想是这样的：

在第一次传递时，找到所有可能的值。
第二次，保留一个字典most_recently_found最近找到每个值的位置。
保留一个优先级队列longest_since该值自找到以来最长的值。
保持最短间隙的最小运行。

现在，当您返回并找到所有值时，您可以遵循如下所示的每个迭代逻辑：

most_recently_found[current_value] = current_position
oldest = longest_since.top()
if current_value == oldest.value:
while oldest.position() != most_recently_found[oldest.position()]:
longest_since.pop()
longest_since.push({value: top.value, position: most_recently_found[oldest.position()]
oldest = longest_since.top()
if current_position - oldest.position() < best_gap:
best_gap = current_position - oldest.position()

关键是对于找到的每个值，您必须更新字典(O(1))，可能必须将其从优先级队列中删除(O(k))，可能必须在优先级队列(O(k))上放置新内容，并且可能必须做一些算术(O(1))。因此，一切都O(n log(k))。

相关内容

最新更新

热门标签：