没有间隔重复的最短子序列

Question

给定一个由 N 个整数组成的未排序数组和一个函数 getNextIndexOf（int k），该函数返回值为 'k' 的下一个元素的索引，如何获得最后一个元素（即索引 N）以最少的调用次数获得 getNextIndexOf（int k）？

*换句话说，用什么值 k₁， k₂， ...， k m 应该调用 getNextIndexOf（int k），以便^{第 m 次}调用返回 '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;
}