Кратчайшая подпоследовательность без дубликатов интервалов

Question

Учитывая несортированный массив из N целых чисел и функцию getNextIndexOf (int k), которая возвращает индекс следующего элемента со значением 'k', как можно получить последний элемент (т. Е.индекс N) с наименьшим количеством вызовов getNextIndexOf (int k)?

* Другими словами, с какими значениями k ₁ , k ₂, ..., k _m если один вызов getNextIndexOf (int k), так что вызов m ^th возвращает 'N', и m настолько мал, насколько это возможно?

** Редактировать: можно предположить, что getNextIndexOf может отслеживать последний возвращаемый индекс
(например, как статический локальныйпеременная в C).При самом первом вызове он просто возвращает индекс первого элемента, равный его аргументу (int k).

Answer 1

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

Я бы попробовал подход ветвления и ограничения.Смотрите здесь .Ветвь на следующем целом числе, которое будет выбрано как k и ограничено количеством уже предпринятых шагов.Держите все ветви в приоритетной очереди и всегда расширяйте заголовок очереди.

Это гарантирует поиск оптимального решения.

РЕДАКТИРОВАТЬ:

Вот некоторый псевдокод:

Let A be the set of all integers that occur in the array.
Let Q be the priority queue

foreach integer k in A do
  Add result of getNextIndexOf(k) to Q

while(Q is not empty && end of array not reached)
  q = head(Q)
  Dequeue(q)

  foreach(integer k in A do)
    Add result of getNextIndexOf(k) to Q (using q)

Answer 2

Возможное решение (написано на Java!):

public static List<Integer> getShortest(int[] array) 
{
   int[] nextChoice = new int[array.length];
   HashMap<Integer,Integer> readable = new HashMap<Integer,Integer>();

   readable.put(Integer(array[array.length-1]), Integer(array.length-1));
   for(int i = array.length-1; i>=0; i--)
   {
      for(Map.Entry<Integer,Integer> entry: readable.entrySet())
      {
         if(entry.getValue().intValue() > nextChoice[i])
            nextChoice[i] = entry.getKey();
      }
      readable.put(Integer(array[i]),i);
   }

   List<Integer> shortestList = new LinkedList<Integer>(array.length);
   for(int i = 0; i < array.length; i++)
      shortestList.add(nextChoice[i]);

   return shortestList;
}