在数组中查找最大值出现的次数

Question

我将尝试查找整数数组中最大值的出现次数。

例如：

int[] ar = [3, 1, 2, 3];

这里，数字 3 出现了两次，因此期望输出结果为 2。

这个代码可以正常运行，我得到的计数是 2，因为数组中最大值 3 出现了两次。

var max = int.MinValue;
var occurrenceCount = 0;

foreach(var x in ar)
{
    if (x >= max) max = x;
}

foreach(var x in ar)
{
    if (x == max) occurrenceCount++;
}

输出结果：2 //occurrenceCount

使用 Linq 更简单，

var occurrenceCount = ar.Count(x => x == ar.Max())

输出: 2 //出现次数

现在没有使用 Linq，有没有更简化或更有效的方法来完成这个任务？

- Hary

---

你想知道如何更高效地进行最大值和计数吗？ - undefined

是的，想要知道数组中的最大值以及最大值出现的次数。 - undefined

你想要哪个：简化还是高效？这总是有一个权衡。如果你设计一个只需遍历列表一次的解决方案，它会更高效，但可能也更复杂。 - undefined

在这里可以找到Max和GetCount的参考。两者都有一个foreach，也许你可以以一种聪明的方式对它们进行重构。 - undefined

@PalleDue，很好的查询，我更喜欢高效的方式。那个问题中的LINQ查询不高效吗？ - undefined

@auburg，虽然不是性能问题，但仍然想知道 Linq 的其他可能用法。 - undefined

Answer 1

至少，你可以合并前两个数组。我仍然会使用Linq解决方案，这更清晰易懂。如果你真的想讨论性能，请先阅读哪个更快？。

下面是一个O(n)的解决方案：

int[] ar = {3, 1, 2, 3, 3, 4, 4};
int max = ar[0];
var occurrenceCount = 1;

for(var i = 1; i < ar.Length; i++)
{
    if (ar[i] > max) {
	max = ar[i];
	occurrenceCount = 1;
    }
    else if (ar[i] == max) {
        occurrenceCount++;
    }
}

WriteLine(max);
WriteLine(occurrenceCount);

在线试用！

• 请注意，您应该处理数组为空的情况。

- aloisdg

Answer 2

我没有使用LINQ，我使用了lambda :)

 int[] ar = new[] { 3, 1, 2, 3 };


        var result = ar.GroupBy(x => x) //values groups
        .Select(x => new
        {
            Number = x.Key,
            Count = x.Count()
        }).OrderByDescending(x => x.Count) //Short
        .FirstOrDefault(); //First Result


 result.Count // how many 

 result.Key   // max number

无 Linq 和无 Lamda

 int[] ar = new[] { 3, 1, 2, 3 };
            Array.Sort(ar);
            Array.Reverse(ar);
            var maxValue = ar[0];
            var occurrenceCount = 0;
            foreach (var item in ar)
            {
                if (item == maxValue)
                    occurrenceCount++;
            }

- go..

---

这仍然是Linq...事实上，如果没有System.Linq，它将无法正常工作。这应该是一个提示 ;) - undefined

Answer 3

基于Max的实现和Enumerable中的GetCount，您可以通过在Max的foreach中添加一个测试来简单地进行因式分解，如下所示：

public static int CountMax(this IEnumerable<int> source)
{
    if (source == null)
    {
        throw new ArgumentException();
    }

    int value = 0;
    bool hasValue = false;
    int count = 0;

    foreach (int x in source)
    {
        if (hasValue)
        {
            if (x > value)
            {
                value = x;
                count = 1;
            }
            else if (x == value)
            {
                count++;
            }
        }
        else
        {
            value = x;
            count = 1;
            hasValue = true;
        }
    }
    if (hasValue)
    {
        return count;
    }

    throw new Exception("no elements");
}

很棒的一点是，将其变得更加通用很容易，比如：

public static int CountMax<TSource>(this IEnumerable<TSource> source) where TSource : IComparable

- Drag and Drop

---

和我的逻辑相同，但速度较慢。你可以跳过第一个元素。看看我的答案。 - undefined

@aloisdg，是的，逻辑相同，但加入了一些故障安全和处理可枚举的功能，适用于实现了IComparable接口的对象。这是从System.LinQ实现中得到的。编写和测试整数和自定义对象只需要稍微多一点时间。 - undefined

OP知道它将使用一个数组。至少切换到IReadOnlyList或IList。为了安全起见，是的，OP应该处理空数组。 - undefined

@aloisdg，它们都实现了IEnumerable接口。所以取决于使用扩展方法来传递所需的类型。从性能上来说，它们应该是“相同”的，几乎不会有明显差异（经过测试：在100万个元素上只有十亿分之一秒的差距）。我并不是要说一个比另一个更好。对我来说，寻找源代码并阅读它们是一种乐趣。 - undefined

Answer 4

你可以尝试更灵活的方法：

using System.Collections.Generic;

namespace ConsoleApp42
{
    class Program
    {
        static void Main (string[] args)
        {
            var array = new int[] { 1, 2, 3, 1, 1, 4, 4, 4, 4, 1, 1, 1 };
            //var array = new string[] { "a", "b", "a", "a" };

            var result = array.MaxCount ();
        }
    }

    public static class Extensions
    {
        public static (long count, T max) MaxCount<T> (this IEnumerable<T> source, IComparer<T> comparer = null)
        {
            if (comparer is null) comparer = Comparer<T>.Default;

            (long count, T max) result = (0, default (T));

            foreach (var element in source)
            {
                if (result.count == 0) // is first element?
                {
                    result.max = element;
                    result.count = 1;

                    continue;
                }

                int compareResult = comparer.Compare (element, result.max);

                if (compareResult == 0) // element == max
                {
                    result.count++;
                }
                else if (compareResult > 0) // element > max
                {
                    result.max = element;
                    result.count = 1;
                }
            }

            return result;
        }
    }
}

- apocalypse

Answer 5

 int[] list = new int[] { 1, 1, 2, 3, 6, 7, 6, 6, 6, 8, 9 };
        Dictionary<int, int> occ = new Dictionary<int, int>();
        for (int i = 0; i < list.Length; i++)
        {
            var val = list[i];
            var count = 0;
            for (int j = 0; j < list.Length; j++)
            {
                if (val == list[j])
                {
                    count++;
                }
            }
            occ.TryAdd(val, count);
        }
        var maxCount = occ.Values.Max();
        var repNumber = occ.FirstOrDefault(x => x.Value == maxCount).Key;

- Khurram Ali