Найти наименьшее окно входного массива, содержащее все элементы массива запросов

Question

Проблема: заданный массив ввода целых чисел размера n и массив запросов из целых чисел размера k, найдите наименьшее окно входного массива, которое содержит все элементы массива запросов, а также в том же порядке.

Я пробовал под подход.

 int[] inputArray = new int[] { 2, 5, 2, 8, 0, 1, 4, 7 }; 
     int[] queryArray = new int[] { 2, 1, 7 }; 

Находит позицию всего элемента массива запросов в inputArray.

public static void SmallestWindow(int[] inputArray, int[] queryArray) 
    { 
     Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>(); 

     int index = 0; 
     foreach (int i in queryArray) 
     { 
      HashSet<int> hash = new HashSet<int>(); 
      foreach (int j in inputArray) 
      { 
       index++; 
       if (i == j) 
        hash.Add(index); 
      } 
      dict.Add(i, hash); 
      index = 0; 
     } 
     // Need to perform action in above dictionary.?? 
    } 

я получил следующего словарь

1. INT 2 -> позиции {1, 3}
2. INT 1 -> Положение {6}
3. INT 7 -> позиции { 8}

Теперь я хочу, чтобы выполнить следующий шаг Findout минимального окна

1. Сравнить int 2 позицию в int 1 позицию. Как (6-3) < (6-1) .. Поэтому я буду хранить 3, 6 в хэш-карте.

2. Будет сравнивать позицию int 1 и int 7, как указано выше.

Я не могу понять, как я буду сравнивать два последовательных значения словаря. Пожалуйста помоги.

Answer 1

Я не вижу, как использование HashSet и Dictionary поможет вам в этом. Если бы я столкнулся с этой проблемой, я бы пошла совсем по-другому.

Один из способов сделать это (не самый эффективный способ) показан ниже. Этот код делает предположение, что queryArray содержит как минимум два элемента.

С некоторыми работами это можно сделать более эффективным. Например, если 'queryArray' содержит [1, 2, 3] и inputArray содержит [1, 7, 4, 9, 1, 3, 6, 4, 1, 8, 2, 3], то приведенный выше код найдет три соответствия (начиная с позиций 0, 4 и 8). Чуть более разумный код мог бы определить, что, когда найдено 1 в позиции 4, так как до него не было найдено 2, что любая последовательность, начинающаяся в первом положении, будет длиннее последовательности, начинающейся в положении 4, и, следовательно, короткого замыкания первого последовательность и начать работу в новой позиции. Однако это немного усложняет код.

Answer 2

Алгоритм:
Для каждого элемента в массиве запроса, хранить в карте М (V → (I, Р)), V является элементом, я является индексом во входной массив, Р позиция в массиве запросов. (Индекс во входной массив для некоторого P является самым большим, так что запрос [0..P] является подпоследовательностью ввода [I..curr])

Итерация через массив.
Если значение является первым членом в массиве запросов: Сохраните текущий индекс как I.
Else: Сохраните значение индекса предыдущего элемента в массиве запросов, например. M[currVal].I = M[query[M[currVal].P-1]].I.
Если значение является последним термином: проверьте, является ли [I..curr] новым.

Сложность
Сложность этого является O (N), где N является размер входного массива.

N.B.
Этот код предполагает, что ни один из элементов не повторяется в массиве запросов. Для этого мы можем использовать карту M (V → listOf ((I, P))). Это O (N Hc (Q)), где Hc (Q), является счетчиком режима для массива запросов ..
Еще лучше было бы использовать M (V → listOf ((LinkedList (I), P))). Если повторяющиеся элементы повторяются последовательно в массиве запросов, мы используем связанный список. Затем обновление этих значений становится O (1). Сложность заключается в том, что тогда O (N hC (D (Q))), где D (Q) - Q с последовательными слагаемыми членами.

Реализация
Пример реализации Java доступна here. Это не работает для повторяющихся элементов в массиве запросов, а также не проверка ошибок и т.д.

Answer 3

Вы хотите не в HashSet, но а (отсортированный) дерево или массив в качестве значения в словаре; словарь содержит сопоставления значений, которые вы находите во входном массиве, в (отсортированный) список индексов, где это значение появляется.

Затем сделайте следующее

• Посмотрите первую запись в запросе. Выберите самый низкий индекс, где он появится.
• Посмотрите вторую запись; выберите самую низкую запись, превышающую индекс первого.
• Посмотрите третий; выберите самый низкий, чем второй. (И т.д.)
• Когда вы дойдете до последней записи в запросе, (1 + последний индекс - первый индекс) является размер самого маленького матча.
• Теперь выберите второй индекс первого запроса, повторите и т. Д.
• Выберите наименьшее число совпадений из любого из стартовых индексов.

(Обратите внимание, что «низкая запись больше» операция поставляется с отсортированных деревьев, или могут быть найдены с помощью двоичного поиска в отсортированном массиве.)

Сложность это примерно O(M*n*log n), где M является длина запроса и n - это среднее число индексов, в которых заданное значение появляется во входном массиве. Вы можете изменить стратегию, выбирая значение массива запросов, которое появляется наименее часто для начальной точки и вверх и вниз оттуда; если есть k этих записей (k < = n), то сложность O(M*k*log n).

Answer 4

После вы получили все позиции (индексы) в inputArray:

2 --> position {0,2} // note: I change them to 0-based array 
1 --> position {5,6} // I suppose it's {5,6} to make it more complex, in your code it's only {5} 
7 --> position {7} 

я использую рекурсию, чтобы получить все возможные пути. [0-> 5-> 7] [0-> 6-> 7] [2-> 5-> 7] [2-> 6-> 7]. Всего 2 * 2 * 1 = 4 возможных пути. Очевидно, тот, у кого есть Min(Last-First), является самым коротким путем (самое маленькое окно), эти числа в середине пути не имеют значения. Вот код.

struct Pair 
{ 
    public int Number; // the number in queryArray 
    public int[] Indexes; // the positions of the number 
} 
static List<int[]> results = new List<int[]>(); //store all possible paths 
static Stack<int> currResult = new Stack<int>(); // the container of current path 
static int[] inputArray, queryArray; 
static Pair[] pairs; 

После структуры данных здесь Main.

inputArray = new int[] { 2, 7, 1, 5, 2, 8, 0, 1, 4, 7 }; //my test case 
queryArray = new int[] { 2, 1, 7 }; 
pairs = (from n in queryArray 
     select new Pair { Number = n, Indexes = inputArray.FindAllIndexes(i => i == n) }).ToArray(); 
Go(0); 

FindAllIndexes является метод расширения, чтобы помочь найти все индексы.

public static int[] FindAllIndexes<T>(this IEnumerable<T> source, Func<T,bool> predicate) 
{ 
    //do necessary check here, then 
    Queue<int> indexes = new Queue<int>(); 
    for (int i = 0;i<source.Count();i++) 
      if (predicate(source.ElementAt(i))) indexes.Enqueue(i); 
    return indexes.ToArray(); 
} 

Метод рекурсии:

static void Go(int depth) 
{ 
    if (depth == pairs.Length) 
    { 
     results.Add(currResult.Reverse().ToArray()); 
    } 
    else 
    { 
     var indexes = pairs[depth].Indexes; 
     for (int i = 0; i < indexes.Length; i++) 
     { 
      if (depth == 0 || indexes[i] > currResult.Last()) 
      { 
       currResult.Push(indexes[i]); 
       Go(depth + 1); 
       currResult.Pop(); 
      } 
     } 
    } 
} 

В конце концов, петля results может найти Min(Last-First) результат (кратчайшее окно).

Answer 5

Алгоритм:

1. получить все индексы в inputArray всех queryArray значения
2. порядка их по возрастанию по индексу
3. с использованием каждого индекса (х) в качестве исходной точки найти первый более высокий индекс (y), так что сегмент inputArray [xy] содержит все queryArray значения
4. содержат только те сегменты, которые имеют queryArray элементы в порядке
5. порядка сегменты по их длине, восходящих

с реализацией #:

Сначала получите все индексы в inputArray всех значений 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(); 

Далее, используя каждый индекс (х) в качестве отправной точки найти первый более высокий индекс (у) таким образом, что сегмент inputArray [х-у] содержит все значения 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 в порядке.

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]); 
    } 
} 

выход:

Smallest window is indexes 3 to 8 

Answer 6

Спасибо всем за ваши входы. Я немного изменил свой код и нашел, что он работает. Хотя это может быть не очень эффективно, но я счастлив решить свою голову :). Пожалуйста, дайте обратную связь

Вот моя пара класс с наличием номера и позиции в качестве переменной

public class Pair 
    { 
    public int Number; 
    public List<int> Position; 
    } 

Вот метод, который возвращает список всех пар.

 public static Pair[] GetIndex(int[] inputArray, int[] query) 
     { 
     Pair[] pairList = new Pair[query.Length]; 
     int pairIndex = 0; 
     foreach (int i in query) 
     { 
      Pair pair = new Pair(); 
      int index = 0; 
      pair.Position = new List<int>(); 
      foreach (int j in inputArray) 
      {      
       if (i == j) 
       { 
        pair.Position.Add(index); 
       } 
       index++; 
      } 
      pair.Number = i; 
      pairList[pairIndex] = pair; 
      pairIndex++; 
     } 
     return pairList; 
    } 

Вот строка кода в главном методе

 Pair[] pairs = NewCollection.GetIndex(array, intQuery); 

     List<int> minWindow = new List<int>(); 
     for (int i = 0; i <pairs.Length - 1; i++) 
     { 
      List<int> first = pairs[i].Position; 
      List<int> second = pairs[i + 1].Position; 
      int? temp = null; 
      int? temp1 = null; 
      foreach(int m in first) 
      { 
       foreach (int n in second) 
       { 
        if (n > m) 
        { 
         temp = m; 
         temp1 = n; 
        }       
       }      
      } 
      if (temp.HasValue && temp1.HasValue) 
      { 
       if (!minWindow.Contains((int)temp)) 
        minWindow.Add((int)temp); 
       if (!minWindow.Contains((int)temp1)) 
        minWindow.Add((int)temp1); 
      } 
      else 
      { 
       Console.WriteLine(" Bad Query array"); 
       minWindow.Clear(); 
       break;      
      } 
     } 

     if(minWindow.Count > 0) 
     { 
     Console.WriteLine("Minimum Window is :"); 
     foreach(int i in minWindow) 
     { 
      Console.WriteLine(i + " "); 
     } 
     } 

Answer 7

Стоит отметить, что эта проблема связана с наибольшей общей проблемой подпоследовательности, поэтому придумывают алгоритмы, которые работают в более чем O (n^2) время в общем случае с дубликатами было бы сложным.

Answer 8

Только в случае, если кто-то заинтересован в реализации C++ с O (Nlog (к))

void findMinWindow(const vector<int>& input, const vector<int>& query) { 
     map<int, int> qtree; 
     for(vector<int>::const_iterator itr=query.begin(); itr!=query.end(); itr++) { 
      qtree[*itr] = 0; 
     } 

     int first_ptr=0; 
     int begin_ptr=0; 

     int index1 = 0; 
     int queptr = 0; 

     int flip = 0; 

     while(true) { 
      //check if value is in query 
      if(qtree.find(input[index1]) != qtree.end()) { 
       int x = qtree[input[index1]]; 
       if(0 == x) { 
        flip++; 
       } 
       qtree[input[index1]] = ++x; 
       } 

       //remove all nodes that are not required and 
       //yet satisfy the all query condition. 
       while(query.size() == flip) { 
       //done nothing more 
       if(queptr == input.size()) { 
        break; 
       } 

       //check if queptr is pointing to node in the query 
       if(qtree.find(input[queptr]) != qtree.end()) { 
        int y = qtree[input[queptr]]; 
        //more nodes and the queue is pointing to deleteable node 
        //condense the nodes 
        if(y > 1) { 
        qtree[input[queptr]] = --y; 
        queptr++; 
        } else { 
        //cant condense more just keep that memory 
        if((!first_ptr && !begin_ptr) || 
         ((first_ptr-begin_ptr)>(index1-queptr))) { 
         first_ptr=index1; 
         begin_ptr=queptr; 
        } 
        break; 
        } 
       } else { 
        queptr++; 
       } 
       } 

      index1++; 

      if(index1==input.size()) { 
       break; 
      } 
     } 
     cout<<"["<<begin_ptr<<" - "<<first_ptr<<"]"<<endl; 
    } 

здесь главное для вызова его.

#include <iostream> 
    #include <vector> 
    #include <map> 

    using namespace std; 

    int main() { 
     vector<int> input; 
     input.push_back(2); 
     input.push_back(5); 
     input.push_back(2); 
     input.push_back(8); 
     input.push_back(0); 
     input.push_back(1); 
     input.push_back(4); 
     input.push_back(7); 

     vector<int> query1; 
     query1.push_back(2); 
     query1.push_back(8); 
     query1.push_back(0); 

     vector<int> query2; 
     query2.push_back(2); 
     query2.push_back(1); 
     query2.push_back(7); 

     vector<int> query3; 
     query3.push_back(1); 
     query3.push_back(4); 

     findMinWindow(input, query1); 
     findMinWindow(input, query2); 
     findMinWindow(input, query3); 
    }