查找出现最小值的数组索引

Question

这让我头晕目眩。正当我以为我明白了的时候，我意识到有些不对劲。我必须使用递归来完成这项作业。有什么提示吗？

/**
 * Uses recursion to find index of the shortest string.
 * Null strings are treated as infinitely long.
 * Implementation notes:
 * The base case if lo == hi.
 * Use safeStringLength(paths[xxx]) to determine the string length.
 * Invoke recursion to test the remaining paths (lo +1)
 */
static int findShortestString(String[] paths, int lo, int hi) {
    int min=lo;
    if (lo==hi)
        return min;
    if (safeStringLength(paths[lo]) < safeStringLength(paths[lo+1])){
        min=lo;
        return Math.min(min, findShortestString(paths, lo+1, hi));
    }
    else{
        min=lo+1;
        return Math.min(min, findShortestString(paths, lo+1, hi));
    }
}

Answer 1

我认为这里有一些东西：

static int findShortestString(String[] paths, int lo, int hi) 
{
    if (lo==hi)
        return lo;

    int ShortestIndexSoFar = findShortestString(paths, lo+1, hi);
    if(safeStringLength(paths[ShortestIndexSoFar]) < safeStringLength(paths[lo]))
        return ShortestIndexSoFar;
    else
        return lo;
}  

static int safeStringLength(String str)
{
    if(str == null)
        return Integer.MAX_VALUE;
    return str.length();
}

解释为什么它有效：
这是一个示例：

[0] ab
[1] abcd
[2] a
[3] abc
[4] ab

显然，索引 2 是最短的。
自下而上思考。从下往上阅读以下内容。
我让它听起来像是每个函数都在与链中位于其上方的函数进行对话。
每行由传递的函数参数引导。

"[0] ab   (paths, 0, 4): return 2, coz he's shorter than me or anyone before us"
"[1] abcd (paths, 1, 4): return 2, coz he's shorter than me or anyone before us"
"[2] a    (paths, 2, 4): return 2, I'm shorter than anyone before me"
"[3] abc  (paths, 3, 4): return 4, coz he's shorter than me or anyone before us"
"[4] ab   (paths, 4, 4): return 4, I'm the shortest; I don't know any better"

所以在代码中，您会看到确实发生了这种情况。
当我们定义 ShortestIndexSoFar 时，每个函数都会知道它之外的所有路径中最短的一条。
就在它之后，函数本身检查其索引是否具有比下面所有路径中最短的路径更短的路径。
继续将最短的索引向上滴，最后一个人将返回最短的索引。

这有道理吗？

Answer 2

由于这是家庭作业，这里有一个帮助您学习的提示：

findShortestString 方法的签名表明您应该使用二分搜索。我为什么要这么说呢？为什么这样做是个好主意？所有其他解决方案都遇到了 Java 中的实际问题......那会是什么？

对于OP以外的人...请不要给出答案...例如通过更正您的答案！

Answer 3

为什么不直接获取每个元素的长度并对返回的长度进行排序以获得排序？像这样。

int[] intArray = {10, 17, 8, 99, 1}; // length of each element of string array
Arrays.sort(intArray);

Answer 4

一种解决方案是这样的

public static final int findShortestString(final String[] arr, final int index, final int minIndex) {

    if(index >= arr.length - 1 ) {
        return minIndex;
    }

    if(-1 == safeStringLength(arr[index])) { 
        return index;
    }


    int currentMinIncex = minIndex;

    if(safeStringLength(arr[minIndex]) > safeStringLength(arr[index+1])){
        currentMinIncex = index + 1;
    }


    return findShortestString(arr, index + 1, currentMinIncex);

}



public static final int safeStringLength(final String string) {

    if( null == string) return -1;

    return string.length();

}

Answer 5

一个简单的解决方案：

/**
     * Uses recursion to find index of the shortest string.
     * Null strings are treated as infinitely long.
     * Implementation notes:
     * The base case if lo == hi.
     * Use safeStringLength(paths[xxx]) to determine the string length.
     * Invoke recursion to test the remaining paths (lo +1)
     */
static int findShortestString(String[] paths, int lo, int hi) {
    if (lo==hi)
        return lo;
    if (paths[lo] == null)
       return findShortestString(paths, lo+1, hi);
    int bestIndex = findShortestString(paths, lo+1, hi);
       if (safeStringLength[lo] < safeStringLength[bestIndex])
           return lo;
    return bestIndex;
}

Answer 6

根据运行 findShortestString 的结果计算 min 没有意义。开始此类问题的最佳方法是仅考虑单个递归步骤，您可以通过考虑仅包含两个要比较的字符串的数组会发生什么来做到这一点。

您要做的就是检查第一个字符串的长度与第二个字符串的长度。但真正的技巧是，您想通过递归调用该函数来测试第二个的长度。这很简单，但需要确定递归的最终情况。当 lo == hi 时，您已成功完成此操作。也就是说，当 lo == hi 时，最短的已知字符串是 lo （它是唯一已知的字符串！）。

好的，回到比较两个字符串。鉴于您知道要比较路径中存储的两个字符串的长度，您可能会执行以下操作（不使用递归）：

if(safeStringLength(paths[0]) < safeStringLength(paths[1])){
    return 0; // paths[0] is shorter
}else{
    return 1; // paths[1] is shorter
}

但是您想要递归 - 并且在递归步骤中您需要以某种方式生成 paths[1] 的 1。我们已经弄清楚了如何做到这一点，当 lo == hi 时，我们返回 lo。因此，递归步骤是“将当前已知的最低字符串长度与已知最佳索引的字符串长度进行比较”——等等，我们有一个函数可以实现这一点！它是findShortestString。因此我们可以将上面的内容修改得更加简洁，并在基本情况中添加得到：

static int findShortestString(String[] paths, int lo, int hi) {
    // base case, no comparisons, the only known string is the shortest one
    if(lo == hi){
        return lo;
    }

    int bestIndex = findShortestString(paths, lo+1, hi);
    return safeStringLength(paths[lo]) < safeStringLength(paths[bestIndex]) ? 
        lo : bestIndex;
}

Answer 7

static int findShortestString(String[] paths, int lo, int hi)
{  
  if (lo==hi)  
    return lo;  
  int ShortestIndexDown = findShortestString(paths, lo, (hi + lo)/2);
  int ShortestIndexUp = findShortestString(paths, (lo+hi)/2+1, hi);
  return SafeStringLength(paths[ShortestIndexDown]) < SafeStringLength(paths[ShortestIndexUp])?ShortestIndexDown:ShortestIndexUp;
}

static int safeStringLength(String str)
{
  if(str == null)
    return Integer.MAX_VALUE;
  return str.length();
}