在集合中找到比它们大的数字

本文关键字：数字 集合 | 更新日期: 2023-09-27 18:11:36

假设我们有一个数字集合，例如{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

但是这个程序不是一个优化的程序。对于同样的问题，有更好的算法吗?

注意:~该程序虽然显然没有任何实时使用，但它将有助于改进算法。

在集合中找到比它们大的数字

你可以从右到左过滤递增的数字序列

的例子:

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];
    }
}
相关文章：