2

我的算法应该从 input 中的当前数字中找到最大的正确数字，例如，给定以下输入：arrayint[]

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扩展方法等更快地解决问题的方法。

4

5 回答 5

6

您可以从右侧一次通过。诀窍是实现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];
于 2013-03-08T08:37:07.170 回答
2

如果您想跳过某些项目并搜索最大值，则非常简单

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

编辑如果你想简单地对一个数组进行排序，那么：

   int[] sorted = arr.OrderByDescending();
于 2013-03-08T08:28:56.370 回答
2

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

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

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

这是一个演示。

因为，我现在更好地看到了这个问题，所以 VLad 的答案看起来是正确的。

于 2013-03-08T08:29:46.977 回答
2

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

于 2013-03-08T10:36:24.183 回答
0

这取每个元素右侧的最大值；

 int[] input = {5, 9, 6, 1, 3, 2};
 int[] output = input
            .Take(input.Length-1)
            .Select( (x,i) => input.Skip(i+1).Max()).ToArray();
于 2013-03-08T08:39:43.263 回答