Алгоритм:
- получить все индексы во входном массиве всех значений queryArray
- упорядочить их по возрастанию по индексу
- , используя каждый индекс (x) в качестве начальногонайти первый более высокий индекс (y) так, чтобы сегмент inputArray [xy] содержал все значения queryArray
- , оставляя только те сегменты, которые имеют элементы queryArray, в порядке
- , упорядочивая сегменты по их длине, по возрастанию
c # реализация:
Сначала получите все индексы во входном массиве всех значений queryArray и упорядочите их по возрастанию по индексу.
public static int[] SmallestWindow(int[] inputArray, int[] queryArray)
{
var indexed = queryArray
.SelectMany(x => inputArray
.Select((y, i) => new
{
Value = y,
Index = i
})
.Where(y => y.Value == x))
.OrderBy(x => x.Index)
.ToList();
Далее, используякаждый индекс (x) в качестве отправной точки находит первый более высокий индекс (y), так что сегмент inputArray [xy] содержит все значения queryArray.
var segments = indexed
.Select(x =>
{
var unique = new HashSet<int>();
return new
{
Item = x,
Followers = indexed
.Where(y => y.Index >= x.Index)
.TakeWhile(y => unique.Count != queryArray.Length)
.Select(y =>
{
unique.Add(y.Value);
return y;
})
.ToList(),
IsComplete = unique.Count == queryArray.Length
};
})
.Where(x => x.IsComplete);
Теперь сохраняем только те сегменты, в которых есть элементы queryArray.order.
var queryIndexed = segments
.Select(x => x.Followers.Select(y => new
{
QIndex = Array.IndexOf(queryArray, y.Value),
y.Index,
y.Value
}).ToArray());
var queryOrdered = queryIndexed
.Where(item =>
{
var qindex = item.Select(x => x.QIndex).ToList();
bool changed;
do
{
changed = false;
for (int i = 1; i < qindex.Count; i++)
{
if (qindex[i] <= qindex[i - 1])
{
qindex.RemoveAt(i);
changed = true;
}
}
} while (changed);
return qindex.Count == queryArray.Length;
});
Наконец, упорядочите сегменты по длине в порядке возрастания.Первый сегмент в результате - это самое маленькое окно в inputArray, которое содержит все значения queryArray в порядке queryArray.
var result = queryOrdered
.Select(x => new[]
{
x.First().Index,
x.Last().Index
})
.OrderBy(x => x[1] - x[0]);
var best = result.FirstOrDefault();
return best;
}
проверить его с помощью
public void Test()
{
var inputArray = new[] { 2, 1, 5, 6, 8, 1, 8, 6, 2, 9, 2, 9, 1, 2 };
var queryArray = new[] { 6, 1, 2 };
var result = SmallestWindow(inputArray, queryArray);
if (result == null)
{
Console.WriteLine("no matching window");
}
else
{
Console.WriteLine("Smallest window is indexes " + result[0] + " to " + result[1]);
}
}
output:
Smallest window is indexes 3 to 8