不包含数组的包含所有元素的最短子数组？

问题描述

问题：找到包含所有元素
的最短子数组的长度示例：1 2 2 3 2 2 1 3
答案：3

解决方案

我假设您要避免的原因数组是您要编写 idiomatic ML代码，因此更喜欢使用纯函数数据结构而不是可变数组？

如果是这样，则可以使用用于滑动窗口方法，几乎​​与使用数组的方法完全相同；唯一的区别是：

• 您不是 O （1）查找，而是有了 O （log m ）查找，其中 m 是不同元素的数量。


• 而不是 O （1）突变，则具有 O （log m ）转换，其中转换返回地图的修改后的副本（共享其大部分节点）。

Problem: Find the length of the shortest subarray that contains all elementsExample : 1 2 2 3 2 2 1 3Answer : 3

I have read that the best approach to this problem is by using the sliding window approach. But this approach requires using arrays. Is there any other efficient approach that does not require to use arrays by storing the number of appearances of each element? ( I would like to use this approach without arrays by writing it in ML )

解决方案

I assume that the reason you want to avoid an array is that you want to write idiomatic ML code, and so would prefer to use a purely functional data structure rather than a mutable array?

If so, then you can use a purely functional red-black tree for the "sliding-window" approach in almost exactly the same way as you would use an array; the only differences are:

• Instead of O(1) lookups, you have O(log m) lookups, where m is the number of distinct elements.
• Instead of O(1) mutations, you have O(log m) transformations, where a transformation returns a modified copy of the map (sharing most of its nodes).

这篇关于不包含数组的包含所有元素的最短子数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！