在集合中查找比他們大的數字

假設我們有一組數字，如{16,17,4,3,5,2}。現在，我們的目標是找到那些比它們正確的元素更多的數字，這些數字比集合中的其他數字更大。表示16比17少是不能考慮的。雖然17共同爲4,3,5和2總是更大，因此將考慮。同樣，4但大於3鄰接少於5將被丟棄。但是5比2更大。而且因爲2是最右邊的元素將永遠被考慮。我已經寫了下面的程序這樣做，它的工作原理在集合中查找比他們大的數字

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace ConsoleApplication2 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 

      var intCollection = new List<int>() { 16,17,4,3,5,2 }; 
      var discardedElements = new List<int>(); 

      for(int i=0;i< intCollection.Count;i++) 
      { 
       for(int j=i+1;j< intCollection.Count; j++) 
       { 
        if (intCollection[i] < intCollection[j]) 
        { 
         discardedElements.Add(intCollection[i]); 
        } 
       } 
      } 
      Console.WriteLine("Successful elements are"); 
      intCollection.Except(discardedElements).ToList().ForEach(i => Console.WriteLine("{0}", i)); 
      Console.ReadKey(); 
     } 
    } 
} 



Result 
------- 
Successful elements are 
17 
5 
2

但這個方案是不是一個優化的一個。針對相同問題的任何更好的算法？請幫忙

N.B.〜該程序雖然顯然沒有任何實時使用，但它有助於改進算法。

非常感謝提前。

來源

2016-10-04 priyanka.sarkar

Optomize內存使用，電池使用，CPU使用率，多芯，分佈式計算？這可能有點太寬泛。 –

如果您只是想減少CPU週期，請將結果元素存儲在新數組中而不是放棄。然後在你的第二回閤中，只要你確認第i個元素無效就可以短路。 –

可以從右到左和過濾器越來越多

的序列go示例：

class Program 
{ 
    static void Main(String[] args) 
    { 
     var intCollection = new List<Int32>() { 16, 17, 4, 3, 5, 2 }; 
     var intResults = new List<Int32>(); 
     var currentMaxValue = Int32.MinValue; 

     for (Int32 i = intCollection.Count - 1; i >= 0; --i) 
     { 
      if (intCollection[ i ] > currentMaxValue) 
      { 
       currentMaxValue = intCollection[ i ]; 
       intResults.Insert(0, intCollection[ i ]); 
      } 
     } 

     Console.WriteLine("Successful elements are"); 
     intResults.ForEach(i => Console.WriteLine("{0}", i)); 
     Console.ReadKey(); 
    } 
}

來源

2016-10-04 08:39:06 Nyavro

這種算法有沒有名字？ –

我不知道它的名字，但我相信它是非常簡單的 – Nyavro

好** O（N）**算法，錯誤的實現有效地將其變成** O（N^2）** –

您可以向左，並保持當前的最大權值迭代，然後進行比較。

// Check empty intCollection 
result.Add(intCollection[intCollection.Count-1]); 
var currentMaxValue = intCollection[intCollection.Count-1]; 
for(int i = intCollection.Count - 2; i >= 0; --i) { 
    if (intCollection[i] > currentMaxValue) { 
     result.Add(intCollection[i]); 
     currentMaxValue = intCollection[i]; 
    } 
}

來源

2016-10-04 08:43:23

雖然誠然你的代碼doesn與C＃版本差別很大，爲什麼要發佈C++問題的答案？ – Martheen

對不起，只需轉到C＃。我比C＃更適合C++。 –

這裏的一個示例實現：

public static IEnumerable<int> NumbersBiggerThanTheFollowingOnes(IList<int> numbers) 
{ 
    if (numbers.Count <= 0) 
     yield break; 

    int max = numbers[numbers.Count - 1]; 
    yield return max; // Last element is considered bigger than the "following" ones. 

    for (int i = numbers.Count - 2; i >= 0; --i) 
    { 
     if (numbers[i] <= max) 
      continue; 

     max = numbers[i]; 
     yield return max; 
    } 
}

樣品測試代碼：

var intCollection = new List<int>() { 18, 10, 13, 16, 17, 4, 3, 5, 2 }; 
Console.WriteLine(string.Join(", ", NumbersBiggerThanTheFollowingOnes(intCollection).Select(x => x.ToString())));

來源

2016-10-04 08:51:26

在集合中查找比他們大的數字

回答

相關問題