0

このような circulatList があるとしましょう

circularList = [12, 62, 76, 92, 3, 7, 12, 19].

上記のリストから最小数を取得する最も効率的な方法は何ですか。

4

6 に答える 6

2

答えの前に、次のことを言わなければなりません。

まず、あなたの言うこととあなたの例が一致しません。[12, 62, 76, 92, 3, 7]循環ソート配列です。ただし、あなたの例:

[12, 62, 76, 92, 3, 7, 12, 19]

は円形ではなく、 の単なる組み合わせですtwo sorted arrays。

そして第二に、それを行う抽象的な方法について話す場合。いくつかの検索アルゴリズム メソッドを変更する必要があります。メソッドの効率は、ケースによって異なります。したがって、アルゴリズムには、最悪のケース、最良のケース、および平均的なケースのパフォーマンスがあります。したがって、「最も効率的な方法」と呼ばれるものは、独自のテスト ケースで試す必要があるものです。

次に、私の答えは、 2 つの並べ替えられた配列の組み合わせから最小の数値を取得する必要がある場合、大胆な比較よりも効率的な方法があります。

int a;
int b = 0;\\your minimum possible value
//l= your array
for(int i=1; i<l.size;i++){
  b=l[i-1];
  a=l[i];
  if(b>a) // find the break point of the two sorted arrays
    if(a<l[0])
      return a;
    else 
      return l[0];
}
return l[0]; // in case the array already sorted(break point in 0 and l.size)

これにより、配列のブレークポイントが見つかったときにループが停止し、最初の数値 (12) と 2 番目の配列の最初の数値 (3) を比較して最小の数値が返されます。

于 2013-08-14T08:15:15.753 に答える
2

@No Idea For Name に加えて:Collections.min(yourCollection)

于 2013-08-14T06:55:46.840 に答える
1

基本的に、任意のリストから最小の要素を取得するためのアルゴリズムは 1 つだけです。

  smallest = unset
  for each element in list:
      if smallest is unset OR element less than smallest:
          smallest = element

これがコードにどのようにマップされるかは、特定のリスト データ構造によって異なります。また、特定のプログラミング言語によっても異なる場合があります。しかし、基本的な構造は同じで、特に効率的な方法はありません。(複雑さはO(N)、Nリストの長さです。)

これを改善できる唯一の方法は、リストを制約することです。たとえば、リストがすでに最小から順にソートされている場合、最小の要素を取得するには、単に最初の要素を取得するだけです。

(しかし、リストをソートするコストは、少なくともO(N)... そしておそらくO(NlogN). 最小値を取得するためのソートは、上記のように反復してテストするよりも効率が悪くなります。)

于 2013-08-14T07:11:16.517 に答える
0

ジェネリック リストに対するシングル スレッド ソリューションは次のとおりです。

int minValue= Integer.MAX_VALUE ;
for(int e: circularList )
    if( e < minValue ) minValue= e ;

最初の要素の位置がわかっている、配列ベースの並べ替えられた循環リストの場合:

minValue= circularList[firstElement] ;

最後の要素の位置がわかっている、配列ベースの並べ替えられた循環リストの場合:

if( lastElement+1 >= circularList.length )
    minValue= circularList[0] ;
else
    minValue= circularList[lastElement+1] ;

最初と最後の要素の位置が不明な配列ベースのソートされた循環リストの場合:

int minValue= Integer.MAX_VALUE ;
int prevValue= Integer.MIN_VALUE ;
for(int e: circularList ) {
    if( e < minValue )
        minValue= e ;
    if( e < prevValue ) {
        break;
    }
    prevValue= e ;
}

汎用リストに対するマルチプロセッサ対応のソリューションは次のとおりです。

int threadCount= 8 ;
int nextStart= 0 ;
MinimumFindingThread[] threads= MinimumFindingThread[threadCount] ;
while( threadCount > 0 ) {
    count= ( circularList.size() - nextStart ) / threadCount ;
    threads[threadCount-1]= new MinimumFindingThread(circularList,nextStart,nextStart+count) ;
    threads[threadCount-1].start();
    nextStart= nextStart+count ;
    threadCount--;
}
int threadCount= 8 ;
int minValue= Integer.MAX_VALUE ;
while( threadCount > 0 ) {
    threads[threadCount-1].join();
    theadMin= threads[threadCount-1].getResult() ;
    if( theadMin < minValue ) minValue= theadMin ;
    threadCount--;
}
class MinimumFindingThread extends Thread {
    int[] list;
    int from;
    int to;
    int minValue;
    public MinimumFindingThread(int[] list,int from,int to) {
        this.list= list ;
        this.from= from ;
        this.to= this.to ;
    }
    public void run() {
        int minValue= Integer.MAX_VALUE ;
        for(int e: this.list[this.from:this.to] )
            if( e < minValue ) minValue= e ;
        this.minValue= minValue ; ;
    }
    public int getResult() {
        return this.minValue ;
    }
}
于 2013-08-14T06:55:55.050 に答える