blocks|key|2435617|text|如果我正确理解问题，我认为你需要做(语言不可知论)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2435618|int+partLen+<-+U.length;
do+{
++++Vector+subSets+<-+S.partition(partLen);
++++foreach+set+I+in+subSets
++++++++if+I.isEqualTo(U)+then
++++++++++++return+true;
++++++++else
++++++++++++partLen+<-+partLen+%2B+1;
}+while+(partLen+<=+S.length);
return+false;|code-block|syntax|javascript|2435619|其中，partition将S分解为任意长度的子集，而isEqualTo可以适当地比较集合。|offset|length|style|CODE|2435620|entityMap^0|0|0|3|9|Q|9|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@$I|R|J|S|K|L]|$I|T|J|U|K|L]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|N|$]]

If I understand the problem correctly I think you need to do (language agnostic)

<pre><code>int partLen &lt;- U.length;
do {
 Vector subSets &lt;- S.partition(partLen);
 foreach set I in subSets
 if I.isEqualTo(U) then
 return true;
 else
 partLen &lt;- partLen + 1;
} while (partLen &lt;= S.length);
return false;
</code></pre>

Where <code>partition</code> will break up S into subsets of whatever length and
<code>isEqualTo</code> can properly compare sets.

blocks|key|2794838|text|有趣的家庭作业，但你还是得自己编码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2794839|好的是你没有告诉我们你使用的是哪种语言，所以我把它当作一个标志，因为你已经决定自己编码，这很好。|2794840|到目前为止，我尽了最大努力：|2794841|对于子字符串(+range+)有2个指针，一个用于范围的开始(较小的索引)，一个用于结束(较大的索引)。两种方法都首先指向数组的开头。|2794842|列出分别在范围内的ABCDE的数量。|2794843|从左到右循环结束。|2794844|对于每个字符，增加列表中字符的数字。如果结果(增加了多少)>+1(查看开始点是否指向相同的字符)。如果是，将开始向前移动和减去1，同时开始指向相关数字>+1的字符，将开始向前移动和减去1。|2794845|如果在列表中所有的>=+1都有ABCDE，那么我们找到了一个候选范围。将其与最短长度(如果有的话)进行比较，如果长度较小，则更新最短长度，并记录新最短范围开始时的索引。|2794846|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|V|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|W|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|X|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|Y|8|@]|9|@]|A|$]]|$1|P|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|Q|$]]

Interesting homework, but you still have to code yourself.

Good thing is you have not told us which language you use, so I take it as a sign as you've decided to code yourself, which is good.

<hr>

My best try so far:

Have 2 pointers for the sub string (range), one for the start (smaller index) of the range and one for the end (larger index). Both point to the beginning of the array first.

Have a list for how many ABCDEs are in the range respectively.

Iterate end from left to right.

For every character, increment the number for the character in the list. If the result (incremented how many) > 1(, see if start points to the same character. If yes, move start forward and minus 1, and) while start points to a character the related number for which > 1, move start forward and minus 1.

If ABCDE in the list all >= 1, then we've found a candidate range. Compare it to the shortest length (if any), and if it is smaller, update the shortest length and record the index for the start of the new shortest range.

blocks|key|1238815|text|这里有一个简单的算法，它只扫描一次数组，不断检查它当前看到的覆盖范围是否比以前看到的覆盖范围短。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1238816|为了简单起见，我将假设我们可以将A、B、C、D和E映射到整数0-4，这样我们就可以很容易地引用数组。我还没有彻底地检查过它，所以请在一两个例子中实际运行它，以确保它能满足您的要求。|1238817|//Cell+0+is+the+last+index+at+which+we+saw+an+A,+cell+1+"+"+saw+a+B,+etc.
int[]+mostRecent+=+new+int[U.length];
mostRecent.setAllValsTo(POSITIVE_INFINITY);

int+shortestRange+=+POSITIVE_INFINITY;+//We+are+trying+to+minimize+this+number.
int+minIndex+=+0;+//The+beginning+index+of+the+range
int+maxIndex+=+POSITIVE_INFINITY;+//The+ending+index+of+the+range.

for(int+i=0;+i<+S.length;+i%2B%2B)+{
++++int+currentValue+=+S[i];+//This+value+will+be+0-4,+corresponding+to+A-E

++++mostRecent[currentValue]+=+i;

++++currentMax+=+mostRecent.findMax();+//beginning+of+current+range
++++currentMin+=+mostRecent.findMin();+//end+of+current+range
++++currentRange+=+currentMax+-+currentMin;

++++if(currentRange+<+shortestRange)+{
++++++++shortestRange+=+currentRage;
++++++++minIndex+=+currentMin;
++++++++maxIndex+=+currentMax;
++++}
}

//currentMax+and+currentMin+now+carry+the+starting+and+ending+indices,+use+them+as+you+see+fit.
return+shortestRange;|code-block|syntax|javascript|1238818|这是O(nk)号，包括n=S.length和k=U.length。仍然有大量的优化可以挤出，但我不知道我是否能降低最坏情况的次序。|1238819|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Here's a simple algorithm which scans the array once, constantly checking if its currently-seen covering range is shorter than the previously seen covering ranges.

For simplicity, I'm going to assume that we can map A, B, C, D, and E to the integers 0-4 so that we can easily reference an array. I haven't checked it thoroughly, so please mentally/actually run it on an example or two to make sure it does what you want.

<pre><code>//Cell 0 is the last index at which we saw an A, cell 1 " " saw a B, etc.
int[] mostRecent = new int[U.length];
mostRecent.setAllValsTo(POSITIVE_INFINITY);

int shortestRange = POSITIVE_INFINITY; //We are trying to minimize this number.
int minIndex = 0; //The beginning index of the range
int maxIndex = POSITIVE_INFINITY; //The ending index of the range.

for(int i=0; i&lt; S.length; i++) {
 int currentValue = S[i]; //This value will be 0-4, corresponding to A-E

 mostRecent[currentValue] = i;

 currentMax = mostRecent.findMax(); //beginning of current range
 currentMin = mostRecent.findMin(); //end of current range
 currentRange = currentMax - currentMin;

 if(currentRange &lt; shortestRange) {
 shortestRange = currentRage;
 minIndex = currentMin;
 maxIndex = currentMax;
 }
}

//currentMax and currentMin now carry the starting and ending indices, use them as you see fit.
return shortestRange;
</code></pre>

This is order O(nk), with n=S.length and k=U.length. There are still plenty of optimizations to squeeze out of it, but I don't know if I could bring the worst-case order lower.

blocks|key|1238865|text|下面是我要怎么做的(用伪代码)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1238866|let+counters[]+be+an+array+such+that+
counters[j]+=+number+of+occurrences+of+character+j,+
where+j+=+0+for+'A',+j+=+1+for+'B',+etc.

build+counters[]+by+scanning+the+original+string+s

let+positions[j][]+be+an+array+listing+the+positions+occupied+by+
character+j+in+the+original+string+s;+note+the+size+of+
positions[j][]+is+equal+to+counters[j]

build+positions[j][]+by+scanning+the+original+string+s;

let+currentPositions[]+be+an+array+such+that+
positions[j][currentPositions[j]]+gives+the+position+of+the+next+
occurrence+of+character+j+in+the+original+string+s

initially+currentPositions[j]+=+0+for+every+j+=+[0+..+u.length]

let+bestLength+=+s.length
let+bestMin+=+0
let+bestMax+=+0
for+i+in+[0+..+s.length]+{
++++for+j+in+[0+..+u.length]+{
++++++++if+(+
++++++++++positions[i][currentPositions[i]]+<+i+and+
++++++++++currentPositions[j]+%2B+1+<+counters[j]
++++++++)
++++++++++currentPositions[j]%2B%2B
++++}
++++let+min+=+s.length
++++int+max+=+0
++++for+j+in+[0+..+u.length]+{
++++++++curPos+=+positions[j][currentPositions[j]
++++++++if+(curPos+>+max)+let+max+=+curPos
++++++++if+(curPos+<+min)+let+min+=+curPos
++++}
++++if+(max+-+min+%2B+1+<+bestLength)+{
++++++++let+bestMin+=+min
++++++++let+bestMax+=+max
++++++++let+bestLength+=+max+-+min+%2B+1
++++}
}

the+shortest+path+is+that+starting+at+bestMin,+ending+at+bestMax,+
and+having+length+bestLength|code-block|syntax|javascript|1238867|复杂性为O(nk)，其中n=+s.length，k=+u.length|1238868|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Here is how I would do it (in pseudocode)

<pre><code>let counters[] be an array such that 
counters[j] = number of occurrences of character j, 
where j = 0 for 'A', j = 1 for 'B', etc.

build counters[] by scanning the original string s

let positions[j][] be an array listing the positions occupied by 
character j in the original string s; note the size of 
positions[j][] is equal to counters[j]

build positions[j][] by scanning the original string s;

let currentPositions[] be an array such that 
positions[j][currentPositions[j]] gives the position of the next 
occurrence of character j in the original string s

initially currentPositions[j] = 0 for every j = [0 .. u.length]

let bestLength = s.length
let bestMin = 0
let bestMax = 0
for i in [0 .. s.length] {
 for j in [0 .. u.length] {
 if ( 
 positions[i][currentPositions[i]] &lt; i and 
 currentPositions[j] + 1 &lt; counters[j]
 )
 currentPositions[j]++
 }
 let min = s.length
 int max = 0
 for j in [0 .. u.length] {
 curPos = positions[j][currentPositions[j]
 if (curPos &gt; max) let max = curPos
 if (curPos &lt; min) let min = curPos
 }
 if (max - min + 1 &lt; bestLength) {
 let bestMin = min
 let bestMax = max
 let bestLength = max - min + 1
 }
}

the shortest path is that starting at bestMin, ending at bestMax, 
and having length bestLength
</code></pre>

Complexity is O(nk), where n = s.length and k = u.length

blocks|key|2435730|text|首先在数组中找到不同的元素，这是O(n)元素。然后用滑动窗法求出所有这些元素都存在的最小跨度。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2435731|您可以看到这里如何找到最小窗口：http://tech-queries.blogspot.com/2010/12/finding-minimum-window-in-array-which.html|offset|length|2435732|entityMap|0|LINK|mutability|MUTABLE|url|http://tech-queries.blogspot.com/2010/12/finding-minimum-window-in-array-which.html|1^0|0|5|2|0|G|2B|1|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|P|8|@]|9|@$D|Q|E|R|1|S]|$D|T|E|U|1|V]]|A|$]]|$1|F|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]|N|$5|I|J|K|A|$L|M]]]]

First find different elements in the array, which is O(n) stuff. Then use sliding window approach to find minimum span, in which all these elements are present.

You can see <a href="http://tech-queries.blogspot.com/2010/12/finding-minimum-window-in-array-which.html" rel="nofollow">here</a> how to find the minimum window: <a href="http://tech-queries.blogspot.com/2010/12/finding-minimum-window-in-array-which.html" rel="nofollow">http://tech-queries.blogspot.com/2010/12/finding-minimum-window-in-array-which.html</a>

In the one dimensional array S , There might be any number of elements that belong to the set 

<pre><code>U:{A,B,C,D,E} 
</code></pre>

and repetition is allowed. 
Example : 

<pre><code>S = {E,B,D,C,A,D,A,E,E,D,B,B,A,C} 
</code></pre>

Question is:

What is the most efficient way in which I can determine the shortest range/path that contains all the elements belonging to set U ,In any given array S ? keep in mind the array can't be sorted. 

In the above example the shortest path is that connecting the first 5 elements of the array S. 

EDIT : 
1) The Number Of Elements of set U isn't constant. 

Thanks in advance.

Find the shortest path in one dimension

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

在一维数组S中，可能存在属于集合的任意数量的元素U:{A,B,C,D,E}  允许重复。例子：S  = {E,B,D,C,A,D,A,E,E,D,B,B,A,C} 问题是：在任何给定的数组S中，确定包含集合U的所有元素的最短范围/路径的最有效方法是什么？请记住，数组不能排序。在上面的例子中，最短的路径是连接数组S的前5...

问在一维中寻找最短路径
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在一维中寻找最短路径EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在一维中寻找最短路径
EN