最有效的方法，從整數集合

問題得到最高的號碼：最有效的方式來獲得整數最有效的方法，從整數集合

我最近在討論這個問題的集合人數最多，我心中有2個解決方案。 1）遍歷集合並找到最高編號（代碼如下） 2）使用排序算法。

第一種方法將有O（n）的效率

int getHighestNumber(ArrayList<Integer> list) 
    {  
     if(list != null && list.size() > 0) 
     { 
      if(list.size() == 1) 
       return list.get(0); 

      int maxNum = list.get(0); 
      for(int item:list) 
      { 
       if(item > maxNum) 
        maxNum = item; 
      } 
      return maxNum;   
     } 
     return null; 
    }

我的問題是「可以在任何排序算法對如任何給定的輸入擊敗它（時間刻度）。如果集合已經排序或不？」有沒有其他方法比這更好？

來源

2017-03-29 chitresh sirohi

除非你知道關於數據的一些信息，否則每個元素可能是最高的 –

如果集合已經排序，你可以找到在O(1)最大元素（假設Collection支持隨機訪問或O(1)訪問Collection的持股量最大元素結束 - 如果最大元素是第一，任何類別會通過它的Iterator給你一個O(1)訪問權限）。但在這種情況下，您不必對其進行排序。

當輸入排序時（至少是O(nlog(n))，如果不是），任何排序都會至少需要O(n)，因爲您無法驗證輸入是否未經過所有元素排序。因此排序算法無法打敗您的O(n)解決方案。

來源

2017-03-29 09:31:24 Eran

好吧，因爲我們事先並不知道輸入是否被排序，那麼這將是解決它的最有效方法嗎？ –

@chitreshsirohi是的，如果不檢查所有元素，您無法知道哪個元素最大。 – Eran

你的問題暗示了它自己的答案。這取決於收集本身的來源。也就是說，您對數據集了解得越多，您就可以更快地設計啓發式方法來獲得所需的答案。

所以，如果您的列表已經排序，然後列表[0]或列表[LEN-1]將是最高的......

二次答案也依賴於「列表將如何往往是搜索？」。如果這是一次性搜索，那麼迭代最高的列表將是最快的。如果您要反覆進行此操作（例如，收集各種指標），那麼首先使用快速排序對它進行排序可能是您的最佳選擇。

來源

2017-03-29 09:36:20 cmroanirgo

你的問題是，有兩個選項來查找未排序列表的最大值。

方法1：使用你的問題getHighestNumber

方案2中提到的方法：排序使用世界上最高效的排序算法，然後將這個列表的最後一個值的列表。

那麼什麼是高效方面的最佳選擇。

我的回答：選項1，如果陣列是沒有排序沒有排序算法可以擊敗選項1

來源

2017-03-29 09:45:29 hunter

與Java 8則可以使用Stream API找到max，但是，這並沒有解決在爲O（n ）的問題。然而，元素訪問比正常迭代器在計算上花費較少;

list.stream().mapToInt(i -> i).max().getAsInt();

來源

2017-03-29 09:51:00 Laazo

這是我最喜歡的說法，我總是用來快速判斷這樣的問題：

你必須使用至少O(N)只是爲了看看所有元素，這是 I/O時間。

不用多思考，它可以說服自己，沒有任何算法在複雜性方面可以擊敗任何O(N)算法。希望它是有道理的。

來源

2017-03-29 09:53:14 shole

最有效的方法，從整數集合

回答

相關問題