急勾配の判定
Posted feedbacks - C#
O(n)ですね。速くなりませんかね？ でも、どうせ全部チェックしなきゃいけないんだから、O(n)が最速でしょうね。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | using System;
static class P
{
static void Main(string[] args)
{
int[] array = { 1, 2, 7, 11, 25 };
Console.WriteLine("急勾配で{0}", IsAggressive(array) ? "す" : "はありません");
}
static bool IsAggressive(int[] array)
{
int sum = 0;
for (int i = 0; i < array.Length; i++)
{
if (sum >= array[i])
return false;
else
sum += array[i];
}
return true;
}
}
|
LINQを使って無難に判定。コレは 3n だから O(n)になるのかな。
Aggregateとかを使おうと思ったんですが、結局はsumを外出しにするのと、Selectで十分だと気づきました。
1 2 3 4 5 6 7 8 9 | static bool IsAggressive(int[] list)
{
int sum = list.Sum();
return list.Reverse().Select(num =>
{
sum -= num;
return sum - num;
}).Any(num => num < 0);
}
|
nobsun
#8891()
Rating1/1=1.00
有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の和は0とします）．
任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」であるかどうかを判定する述語関数を定義してください．
必須ではありませんが，効率についてコメントがあれば面白いかもしれませんね．
[ reply ]