1

Java で特定の範囲にある配列から要素を取得したい場合、それを行う最も効率的な方法は何でしょうか?

例えば

配列

A = [25,32,54,23,76,34];

そして、私は取得したいです

element between 45 and 55.

それが要素です：

54

では、それを得る最も効率的な方法は何でしょうか？

4

5 に答える 5

3

配列を繰り返し検索する場合は、配列をソートし、バイナリ検索を使用して下限と上限を見つけることが最善の方法です。これにより、十分な検索で償却すると、O(log n) のパフォーマンスが得られます。

それが1回限りの検索である場合、他の人が示唆しているように、配列をスキャンして各要素を下限/上限と比較するよりも良いことはできません-これはO(n)です。

于 2012-11-01T05:35:10.620 に答える
0

与えられたレンジャーの間にいくつの要素があるかを知るためには、n個の比較を計算するn個の要素があるので、少なくとも1回はすべての要素をトラバースする必要があるため、O（n）の複雑さは最小限に抑えられます。複雑さはO（n）です。

ソリューションAFAIKに来る。

n <-array.length;

for(int i=0;i<n;i++)
{
  if((a[i]<upperLimit) && (a[i]>lowerLimit))
   {
      SOP(a[i]);//or store in temp array based on your requirement
   } 
}
于 2012-11-01T05:22:19.700 に答える
0

クエリに答えるには、配列に含まれる要素 (a と b の間の要素) を知る必要があります。

n個のそのようなクエリに答える場合は、おそらく配列をソートし（n log n）、a以上の最も近い要素（aはaとbより小さい）と、またはより小さい最も近い要素を見つけることができます二分探索 (n log n + n log n) を使用して b に等しくし、それらの間の要素を取得します。

a と b の間の要素数が小さい場合、おそらく n 個のクエリで O(n log n) の複雑さを達成でき、各クエリの価値は平均で O(log n) になりますが、a と b の間の要素数がn のオーダーの場合、各クエリは O(n) の複雑さに値します。

于 2012-11-01T05:35:43.927 に答える
0

あなたはこのようなことを試すことができます

int dLimit=45, uLimit =55, result[] = new int[A.length],j=0;
for(int i : A){
    if(i>dLimit && i<uLimit)
        result[j++] = i;
}
于 2012-11-01T05:10:04.187 に答える
0

それが最も効率的かどうかはわかりませんが、私はこのようなことをします。

    int[] rangeTracker = new int[100];
int rangeTrackIndex = 0;
For (int j = 0; j < A.getLength(); j++) {

     if ((A[j] >= 45) && (A[j] <= 55)) {
          rangeTracker[rangeTrackIndex] = A[j];
          rangeTrackIndex++;
}
}
For (int j=0; j < rangeTracker.getLength(); j++) {
     System.out.println(rangeTracker[j]);
}

構文の一部が間違っている可能性があり、これは間違った方法である可能性がありますが、Java を使用して約 2 か月しか経っていません。さらに、プログラミングを始めて約 4 か月しか経っていません。これが役立つことを願っています。

于 2012-11-01T05:18:44.280 に答える