我的算法应该从输入的当前数中找到最大正确的数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];
关于c# - 数组算法中从当前数中找出最大的正确数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15289621/