Entry

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

2008年12月11日

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

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

codeなにがし::最大値の取得(java)

これで,

ソートでググれ

codeなにがし::最大値の取得(java)

とか,

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

codeなにがし::最大値の取得(java)

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

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) でいける。配列を壊すこともない。

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

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN