0

正如标题所说，是否有任何有效的方法可以使用递归找到数组中的第二大元素？

4

6 回答 6

4

基于分区的选择算法本质上是递归的，它可以让您选择k数组中的第 'th 个元素，因此使用它 - 您实际上可以找到任何的答案k，包括k = n-1（您的情况）。

O(n)平均而言，这是在相当低的常数下完成的。

于 2013-01-10T15:50:52.970 回答
2

如果对数组一无所知O(n)，无论是递归还是迭代，你都不能做得更好。

只需递归地传递数组，同时传递两个最大的元素并在找到更大的值时替换它们。

find_largest(array_begin, largest, secondLargest)
    if (array_begin = NULL)
       return secondLargest
    if (array_begin.value > largest)
       secondLargest = largest
       largest = array_begin.value
    return find_largest(array_begin+1, largest, secondLargest)

largest并且secondLargest最初可以设置为您希望在数组中找到的最小值。

你是对的，排序（至少完全排序）是矫枉过正的。

于 2013-01-10T15:48:13.470 回答
1

O(n)像这样的东西：

int findSecondLargest(int[] arr, int index, int largest, int secondLargest) {
    if(index == arr.length) {
        return secondLargest;
    }
    int element = arr[index];
    if(element > secondLargest) {
        if(element > largest) {
            return findSecondLargest(arr, index + 1, element, largest);
        } else {
            return findSecondLargest(arr, index + 1, largest, element);
        }
    }
    return findSecondLargest(arr, index + 1, largest, secondLargest);
}
于 2013-01-10T15:50:53.470 回答
0 
    public void recurs(int[] data, int ind, int max1, int max2){
        if(ind<data.length){
            if(data[ind]>max1){
                int temp = max1;
                max1 = data[ind];
                max2 = temp;
            } else if(data[ind]>max2){
                max2 = data[ind];
            }
            recurs(data, ind+1, max1, max2);
        } else {
            return max2;
        }
        return -1;
    }

调用它：recurs(dataX, 0, Integer.MIN_VALUE, Integer.MIN_VALUE);

于 2013-01-10T15:55:26.467 回答
0

本能地，您可以扫描数组并对每个值进行两次比较。无论如何，你需要 O(n) 来解决这个问题。它足够快。

在不必要的时候尽量避免递归，因为它不是免费的。

于 2013-01-10T16:24:21.840 回答
0

如果您通过递归进行，那么您最多必须进行 3(n)/2-2 比较，但为了获得更好的解决方案，请将此问题视为具有 n 个节点的二叉树。然后将进行 n-1 比较以找到最大的和 log(n)-1 比较以找到第二大的。但有些人认为它需要 n + log(n) 比较。

于 2014-03-16T10:14:39.100 回答