不使用 IComparable<T> 接口查找最大/最小元素

Question

不使用 IComparable<T> 接口查找最大/最小元素

5

假设我有以下内容：

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

public List<BooClass> booList;

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

编辑：抱歉，为了简化示例，我打算将所有字段都设为公共字段。我知道可以用linq实现，但我想知道Find方法是否有一个简单的单行条件。

- Rich Oliver

6个回答

5

您需要通过一个公共属性（我们称之为 Field3）来暴露 field3，可以使用以下代码：

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

请查看Enumerable.First和 Enumerable.Min

注意：因为每次迭代都通过Min遍历列表，所以它的时间复杂度为O(n^2)（二次时间）。对于足够大的集合，相比于Saeed Amiri的答案，它会遇到严重的性能问题，而后者的时间复杂度为O(n)（线性时间）。

- Jason Down

抱歉，有点过于着急了。我现在会立即纠正。 - Jason Down

抱歉，没有将字段公开是一个疏忽。 - Rich Oliver

3

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

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

只需将您的属性公开。

- Saeed Amiri

BooClass earliest = booList.First(i => i.field3 == booList.Min(j => j.field3)); //我认为这是最短的语法，但它比Linq方法需要更长的时间吗？ - Rich Oliver

@RichOliver，使用更短的语法有什么好处？我的代码运行时间为O(n)，而你的语法或Jason的答案运行时间为O(n^2)，那我为什么要提供更慢的答案呢？此外，我可以只用一个查询来编写它，但为了使其更易读，我将其分成两行。 - Saeed Amiri

我更喜欢你的方法，@SaeedAmiri。一旦集合的大小足够大，我的答案性能将非常差。 - Jason Down

@SaeedAmiri 这些语句不是会评估为O(n + m)吗？ - Samir Banjanovic

@CoffeeMuncher，我假设整个输入大小为n。 - Saeed Amiri

显示剩余2条评论

3

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

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

- shenhengbin

dknaack以类似的方式回答了，为什么你在10分钟后添加这个呢？ - Saeed Amiri

抱歉，我不知道时间限制。我刚看到它... :( - shenhengbin

2

相似但不完全相同。我更喜欢这种语法。 - Jeff Reddy

0

如果您不想定义MinBy方法，可以使用聚合函数：

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

为了支持空列表，请使用null作为聚合的种子，如下所示：

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

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

- Steven Waterman

0

据我所知，仅使用List<T>.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)，但我想这可能会被认为是作弊...）

- afrischke

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phoog · Accepted Answer

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<>提供程序，则此方法无法使用。（更准确地说，它效率低下，因为它从数据库中提取对象并在本地处理它们。）有关不执行此操作的解决方案，请参见Saeed's answer。

您还可以基于该方法创建扩展方法，但由于我现在正在使用手机，所以我将把实现留给读者作为“练习”。