4

私は整数配列を持っていvalue[]ます。長さは任意です。

最小の数を見つける必要があります。インタビュー通りの問題に取り組んでいます。Time Exceededというエラーが表示されます。反復処理が悪化するため、最小値の計算速度を上げる必要があります。

私はJavaコレクションなどを使用することに興味があるので、コードを改善するための提案をしてください。

int mini=value[0];
for (int i = 1; i < noinps; i++) {
    if(mini>value[i]) {
        mini=value[i];
    }
}
System.out.println(mini);
4

5 に答える 5

9

配列内の最小要素または最大要素を見つけるためのより良いアルゴリズムはありません。すべての要素に目を向ける必要があります。たとえば、入力の読み取りなど、他の場所で時間を失う可能性があります。

于 2012-05-01T16:07:41.587 に答える
6

このアルゴリズムは、配列の最小値を見つけるのに適しているようです。arraym に含まれている可能性のある要素について何もわかっていない場合は、各要素を検査する必要があるため、パフォーマンスは線形になります (配列内の要素の数に正比例します)。

要素が完全に順序付けされている場合は、最初 (または最後、依存または順序付け) の要素を検索するだけです (一定時間のパフォーマンス)。

要素が半順序付けされている場合 (ヒープ構造など)、二分探索のような手法 (log(n) パフォーマンス) で見つけることができます。

要素が順序付けされていなくても、特定の値よりも小さくできないことがわかっている場合は、可能な限り小さい値を見つけたら検索を停止できます。

タイムアウトの問題に戻ります。要素が順序付けられておらず、他に制限がない場合、アルゴリズムは問題ないため、タイムアウトはプログラムの他の部分から発生する必要があります (たとえば、コンソールから読み取ろうとしているが、データはファイルにあります）

于 2012-05-01T16:08:10.613 に答える
2

配列を要素のストレージ構造として使用する場合、すべての要素をループして最小要素を見つける以外に選択肢はありません。ただし、配列を一度だけループしているため、アルゴリズムは O(n) の複雑さで正常に機能します。

配列のサイズが非常に大きい場合、反復はさらに悪化します。その場合、アレイ以外に選択肢がない場合は、ストレージ領域としてアレイを使用しないことをお勧めします。次に、要素を配列自体に入れる前に、すべての要素を検査してみてください。そうすれば、最小要素を見つけるために配列を反復する必要がなくなります。

コレクションを使用するには、これが最善のアプローチです

ArrayList arrayList = new ArrayList();
//Add elements to Arraylist
arrayList.add(new Integer("23"));
arrayList.add(new Integer("1"));
arrayList.add(new Integer("134"));
arrayList.add(new Integer("22"));
arrayList.add(new Integer("0"));

/*
   To find maximum element of Java ArrayList use,
  static Object max(Collection c) method of Collections class.

   This method returns the maximum element of Java ArrayList according to
   its natural ordering.
*/

Object obj = Collections.max(arrayList);

System.out.println("Maximum Element of Java ArrayList is : " + obj);
于 2012-05-01T16:26:28.467 に答える
0

2 つのスレッドを使用します。それぞれが配列の半分を取り、半分の最小値を見つけて、結果を変数に書き込みます。その後、メインスレッドで 2 つの結果を比較します。

于 2012-05-01T16:21:12.553 に答える
0

最小数を取得する簡単な方法.. 

 import java.util.Arrays;
    public class demoClass {
        public static void main(String[] args) {

                  // consider the below array of data
                    int[] numbers = {12,22,32,43,53};

                   // first sort the array using sort keyword
                   Arrays.sort(numbers);

                 System.out.println("Smallest Number = "+numbers[0]);
        }
    }
于 2013-05-15T13:08:45.597 に答える