[topic] リストの並び
Posted feedbacks - Scala
N = 50000 のときの速度を考えて実装。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | object Doukaku183 extends Application {
def least [A <% Ordered[A]](a: A, b: A) = if (a < b) a else b
def greatest[A <% Ordered[A]](a: A, b: A) = if (a > b) a else b
def check[A <% Ordered[A]](ls: List[A]) = {
def loop(ls: List[A], min: A, max: A): boolean = ls match {
case Nil => true
case h :: t => {
if (min <= h && h <= max) false
else loop(t, least(min, h), greatest(max, h))
}
}
ls.reverse match {
case Nil => true
case h :: t => {
loop(t, h, h)
}
}
}
{
println(check(List(1, 5, 4, 2))) // => true
println(check(List(1, 2, 3))) // => true
println(check(List(825, 102, 811, 140, 812, 125, 263))) // => false
println(check(List(824, 102, 811, 140, 810, 155, 263))) // => true
println(check(List(5, 4, 3, 2, 1))) // => true
println(check(List(4, 2, 5, 3, 1))) // => false
println(check((1 to 50000).toList)) // => true
println(check(100 :: (1 to 49999).toList)) // => false
}
}
|
coze #6421() Rating0/0=0.00
数値のリストがあります。リストのサイズは N です。 ls[0]がリストの先頭要素、ls[N-1]が最後の要素です。 問題: 入力として与えられたリストが次の条件を満たすかどうかを求めてください。 for (int i = 0; i < N-1; i++) { ls[i] != ls[i+1] である ls[i] < ls[i+1] なら、ls[i] < ls[k] である(for all k = i+1 to N-1) ls[i] > ls[i+1] なら、ls[i] > ls[k] である(for all k = i+1 to N-1) } N の範囲は 3 <= N <= 50000 です。実行例を示します。 > check([1, 5, 4, 2]) True > check([1, 2, 3]) True > check([825, 102, 811, 140, 812, 125, 263]) False > check([824, 102, 811, 140, 810, 155, 263]) True > check([5, 4, 3, 2, 1]) True > check([4, 2, 5, 3, 1]) False[ reply ]