在数组算法中从当前数字中找到最大的正确数字

本文关键字：数字 数组 算法 | 更新日期: 2023-09-27 18:02:48

我的算法应该从输入array的当前数字中找到最大的右数，例如，给定以下int[]输入:

5、9、6、1、3、2

我的算法将输出:

9、6、3、3、2、2

下面是我当前的代码:

public static int[] FindGreatestRightNumber(int[] input)
{
    var output = new int[input.Length];
    for (var i = 0; i < input.Length; i++)
    {
        int maxRightNumber = (i == input.Length - 1 ? input[i] : 0);
        for (var j = i+1; j < input.Length; j++)
        {
            var currentNumber = input[j];
            if (maxRightNumber < currentNumber)
                maxRightNumber = currentNumber;
        }
        output[i] = maxRightNumber;
    }
    return output;
}

我被告知它可以更快，怎么做到的?任何想法?

更新:请不要在您的答案中使用LINQ，我想熟悉使用简单代码更快地解决问题的方法，没有LINQ, IEnumerable扩展方法等

在数组算法中从当前数字中找到最大的正确数字

您可以从右侧一次完成此操作。诀窍是实现maxRightVal(n) = max(maxRightVal(n+1)， values(n+1)):

var output = new int[input.Length];
output[input.Length-1] = input[input.Length-1];
for(int i = input.Length - 2; i >= 0; i--)
    output[i] = output[i+1] > input[i+1] ? output[i+1] : input[i+1];

为什么不直接使用Enumerable.Max()方法?

返回Int32值序列中的最大值。

int[] input = new int[] { 5, 9, 6, 1, 3, 2 };
int biggest = input.Max();
Console.WriteLine(biggest); // 9

这是一个DEMO。

由于我现在看问题看得更清楚了，VLad的答案看起来是正确的。

非常简单，如果你想跳过一些项目并搜索最大值

int[]arr = {5, 9, 6, 1, 3, 2};
int currentIndex = 2;
int currentValue = 6;
int max = arr.Skip(currentIndex).Where(f => f > currentValue).Max();

EDIT如果您只想对数组进行简单排序，则:

   int[] sorted = arr.OrderByDescending();

从(n-2)个元素开始，保持当前的max数组，初始化第n个元素。如果当前元素大于max数组中的元素，则继续更新它。直到到达第一个元素。

取每个元素右边的最大值;

 int[] input = {5, 9, 6, 1, 3, 2};
 int[] output = input
            .Take(input.Length-1)
            .Select( (x,i) => input.Skip(i+1).Max()).ToArray();
相关文章：