不使用 IComparable查找最大/最小元素

Question

假设我有以下内容：

public Class BooClass
{
   public int field1;
   public double field2;
   public DateTime field3;
}

public List<BooClass> booList;

例如，如何使用 booList.Find() 获取 field3 中最早时间的元素

编辑抱歉，为了简化示例，我的意思是公开所有字段。我知道可以在 linq 中做到这一点，我想知道 Find 方法是否有一个简单的单行条件。

Answer 1

F# 有方便的 minBy 和 maxBy 运算符，我喜欢将其实现为 C# 扩展方法，因为 Linq 库省略了它们。这是一项工作，但只是一点点，它允许您避免复杂的表达式，例如

var earliest = booList.First(b => b.Field3 == booList.Min(e => e.Field3));

相反，您可以输入以下内容：

var earliest = booList.MinBy(b => b.Field3);

一个简单的实现：

static T MinBy<T, C>(this IEnumerable<T> sequence, Func<T, C> keySelector)
{
    bool first = true;
    T result = default(T);
    C minKey = default(C);
    IComparer<C> comparer = Comparer<C>.Default; //or you can pass this in as a parameter

    foreach (var item in sequence)
    {
        if (first)
        {
            result = item;
            minKey = keySelector.Invoke(item);
            first = false;
            continue;
        }

        C key = keySelector.Invoke(item);
        if (comparer.Compare(key, minKey) < 0)
        {
            result = item;
            minKey = key;
        }
    }

    return result;
}

这也比顶部的复杂表达式更有效，因为 MinBy 迭代序列恰好一次，而表达式迭代多次且小于或等于两次。当然，排序然后取出第一项需要排序，这是 O(n log n)，而这只是 O(n)。

正如 Saeed Amiri 所指出的，如果您依赖 Linq to SQL 或任何其他 IQueryable 提供程序，则此方法不起作用。 （更准确地说，它工作效率低下，因为它从数据库中提取对象并在本地处理它们。）有关不执行此操作的解决方案，请参阅 赛义德的回答。

您还可以基于该方法创建一个扩展方法，但由于我现在正在使用手机，因此我将把实现保留为众所周知的“读者练习”。

Answer 2

您需要通过公共属性公开 field3（我们将其称为 Field3），但您可以使用以下内容：

var earliest = booList.First(b => b.Field3 == booList.Min(e => e.Field3));

查看 Enumerable.First 和 Enumerable.Min

注意：这的时间复杂度为 O(n^2)（二次方时间），因为它通过以下方式遍历列表每次迭代Min。与 Saeed Amiri 的答案，运行时间为 O(n)（线性时间）。

Answer 3

使用 OrderBy 然后获取第一个元素

var result = booList.OrderBy(p => p.field3).FirstOrDefault();

Answer 4

O(n) 方法如下。首先找到最小日期（对于 field3），然后找到具有此最小日期的第一个对象：

var minDate = booList.Min(x=>x.field3);
var item = booList.First(x=>x.field3 == minDate);

只需将您的属性公开即可。

Answer 5

据我所知，仅使用 List.Find 无法检索具有最小日期的 BooClass 对象。当然你可以这样做：（

void Main()
{
    List<BooClass> booList = new List<BooClass> { 
                        new BooClass { field3 = DateTime.MaxValue}, 
                        new BooClass { field3 = DateTime.Now },
                        new BooClass { field3 = DateTime.MinValue }};
    var pred = GetPredicate(booList);
    var result = booList.Find(pred);
}

public Predicate<BooClass> GetPredicate(List<BooClass> boos)
{
    var minDate = boos.Min(boo => boo.field3);   
    return bc => bc.field3 == minDate;
}

就像 Saeed 的解决方案一样 - 时间复杂度也为 O(n)），但我想这会被认为是作弊......

Answer 6

如果您不想定义 MinBy 方法，则可以使用聚合，如下所示：

booList.Aggregate((currMin, test) => currMin < test ? currMin : test);

要支持空列表，请使用 null 为聚合播种，如下所示：

booList.Aggregate(null, (currMin, test) => null == currMin || currMin > test ? test : currMin);

此解决方案的时间复杂度为 O(n)