使用遞歸在數組中尋找第二大元素

正如標題所說，是否有任何有效的方法來找到數組中使用遞歸的第二大元素？使用遞歸在數組中尋找第二大元素

來源

2013-01-10 Neel

向我們顯示您的代碼，並告訴您它是否有效 –

您是否必須使用遞歸？沒有，很容易做到。 – Henry

效率和遞歸是兩個不同的方向。 –

partition based Selection algorithm本質上是遞歸的，它可以讓你選擇k「個數組中的元素，因此使用它 - 實際上你可以找到任何k答案，包括k = n-1（你的情況）。

這在O(n)平均具有相當低的常量完成。

來源

2013-01-10 15:50:52 amit

如果對該陣列沒有任何瞭解，無論是遞歸還是迭代，您都不可能比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-10 15:48:13

如果沒有關於該陣列的信息，我該如何設置最小值？你的意思是第一個元素？ – Neel

@沒有額外的信息我的意思是 - 即如果你知道數組排序，你可以在'O（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-10 15:50:53

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; 
    }

叫它：重複（DATAX，0，Integer.MIN_VALUE的，Integer.MIN_VALUE的）;

來源

2013-01-10 15:55:26

本能地，您可以掃描數組並對每個值進行兩次比較。無論如何，你需要O（n）來解決問題。速度夠快。

嘗試避免遞歸，因爲它不是必需的，因爲它不是免費的。

來源

2013-01-10 16:24:21

如果你通過遞歸實現，那麼你最多隻能做3（n）/ 2-2比較，但爲了更好的解決方案，把這個問題看作一個有n個節點的二叉樹。然後將有n-1比較找到最大和log（n）-1比較第二大。但有些人認爲它需要n + log（n）比較。

來源

2014-03-16 10:14:39 Yeshwant

使用遞歸在數組中尋找第二大元素

回答

相關問題