プログラミングメモ - 最大値を求めるのにソートはダメ。絶対。

2008/12/11

codeなにがしのこちらから。

x[i]に多量の数値の配列を行い, その最大値を表示したいのですが, 最大値の取得について教えていただけませんか?

これで,

とか,

配列の中身を変更していいなら、Arraysクラスの sortメソッドを使うのが一番単純だと思いますが…。

ということなのだけれど,最大値を取得するだけなのに,高価なソートを使うってのは,富豪的プログラミングの極みだなぁ,と思った。そんなに手間じゃないし,普通に書けばいいのではねいだろうか。

import java.util.*;

public class MaxNum {
  public static void main(String args[]) {
    int randMax = 1000;
    Random rand = new Random();
    ArrayList<Integer> x = new ArrayList<Integer>();

    // create random number
    for (Integer i = 0; i < 10; i++) {
      x.add(i, rand.nextInt(randMax));
    }
    Integer size = x.size();
    // print array
    for (Integer i = 0; i < size; i++) {
      System.out.println("x[" + i + "]:" + x.get(i));
    }
    // search max
    Integer max = x.get(0);
    for (Integer i = 0; i < size; i++) {
      max = (max < x.get(i)) ? x.get(i) : max;
    }
    System.out.println("max: " + max);
  }
}

探してるのは最後のループだけ。わざわざ書くのが恥ずかしくなってくる。まぁ,これもあんまりいい書き方じゃないんですけど,ほとんどイディオムです。ともあれ,これなら O(N) でいける。配列を壊すこともない。

なんか,最近脊髄反射的にエントリを立ててる感じがする……自重しよう。

Site Navigation
SNS Accounts (@aian)

普段はここら辺に住んでいます.