2

私のアルゴリズムは、たとえば次の入力が与えられた場合、入力の現在の数値から最大の正しい数値を見つける必要があります。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を使用して問題を解決するためのより速い方法に精通したいと思います。LINQIEnumerable

4

5 に答える 5

6

右側から 1 回のパスでこれを行うことができます。トリックは、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 番目の要素で初期化された現在の最大配列を維持します。現在の要素が最大配列の要素よりも大きい場合は、更新を続けます。これを最初の要素に到達するまで続けます。

于 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 に答える