时间戳

首页 > 解决方案 > c#递归查找最大值（最快）

c# - c#递归查找最大值（最快）

问题描述

我对这个没有想法。最初我自己尝试过，然后从 SO 和 google 复制，它适用于除一个以外的所有情况，但是在我的作业中仍然没有找到对特定测试用例足够快的递归算法：/

无论如何，为什么会这样：

        public static int FindMaximum(int[] array)
        {
            if (array is null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            if (array.Length == 0)
            {
                throw new ArgumentException(null);
            }

            return FindMaxRec(array, array.Length);
        }

        public static int FindMaxRec(int[] arr, int n)
        {
            if (n == 1)
            {
                return arr[0];
            }

            return Math.Max(arr[n - 1], FindMaxRec(arr, n - 1));
        }

不适用于此TestCase？：

        [Test]
        [Order(0)]
        [Timeout(5_000)]
        public void FindMaximum_TestForLargeArray()
        {
            int expected = this.max;
            int actual = FindMaximum(this.array);
            Assert.AreEqual(expected, actual);
        }

编辑1：

虽然这很好用，但我需要递归：

        public static int FindMaximum(int[] array)
        {
            if (array is null)
            {
                throw new ArgumentNullException(nameof(array));
            }

            if (array.Length == 0)
            {
                throw new ArgumentException(null);
            }

            int maxValue = int.MinValue;

            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] > maxValue)
                {
                    maxValue = array[i];
                }
            }

            return maxValue;
        }

标签： c#arraystestingrecursionmax

解决方案

您可以尝试将数组分成两部分：

public static int FindMaximum(int[] array) {
  if (null == array)
    throw new ArgumentNullException(nameof(array));
  if (array.Length <= 0)
    throw new ArgumentException("Empty array is not allowed.", nameof(array));

  return FindMaxRec(array, 0, array.Length - 1);
}

private static int FindMaxRec(int[] array, int from, int to) {
  if (to < from)
    throw new ArgumentOutOfRangeException(nameof(to));
  if (to <= from + 1)
    return Math.Max(array[from], array[to]);

  return Math.Max(FindMaxRec(array, from, (from + to) / 2),
                  FindMaxRec(array, (from + to) / 2 + 1, to));
}

演示：

Random random = new Random(123);

int[] data = Enumerable
  .Range(0, 10_000_000)
  .Select(_ => random.Next(1_000_000_000))
  .ToArray();

Stopwatch sw = new Stopwatch();

sw.Start();

int max = FindMaximum(data);

sw.Stop(); 

Console.WriteLine($"max  = {max}");
Console.WriteLine($"time = {sw.ElapsedMilliseconds}");

结果：

max  = 999999635
time = 100

推荐阅读