0

タイトルが示すように、再帰を使用して配列内で2番目に大きい要素を見つける効率的な方法はありますか？

4

6 に答える 6

4

パーティションベースの選択アルゴリズムは本質的に再帰的であり、配列内の 'th 要素を選択できる(あなたの場合)を含むk任意の の答えを実際に見つけることができkk = n-1

これはO(n)平均してかなり低い定数で行われます。

于 2013-01-10T15:50:52.970 に答える
2

O(n)配列について何も知られていない場合、それが再帰的であろうと反復的であろうと、より良いことはできません。

2 つの最大の要素を渡し、より大きな値が見つかった場合はそれらを置き換えながら、配列を再帰的に通過するだけです。

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

再帰によって行う場合、せいぜい 3(n)/2-2 の比較を行う必要がありますが、より良い解決策として、この問題を n 個のノードを持つバイナリ ツリーと考えてください。次に、最大のものを見つけるために n-1 の比較があり、2 番目に大きいものについては log(n)-1 の比較があります。しかし、n + log(n) の比較が必要だと主張する人もいます。

于 2014-03-16T10:14:39.100 に答える
0

本能的に、配列をスキャンして、すべての値を 2 回比較することができます。とにかく、問題を解決するには O(n) が必要です。それは十分に速いです。

フリーではないため、不要な場合は再帰を避けるようにしてください。

于 2013-01-10T16:24:21.840 に答える