比方说,我们有像{} 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();
}
}
}
结果
Successful elements are
17
5
2
但这个方案是不是一个优化的一个。任何更好的算法同样的问题?
注:2,虽然很明显,程序没有任何实时使用,但它会提高算法的帮助。
你可以从右边到左边和过滤的数字递增序列
例:
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();
}
}
这里有一个简单的实现:
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())));
您可以从左边到右边重复,并保持然后比较当前最大值。
// 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];
}
}