1

次のプログラミングの質問を解決しています。

Given a sorted integer array and a number, find the start and end indexes of the number in the array. 

Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6} 
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1} 

Complexity should be less than O(n)

私の解決策は次のとおりです。

public static void  findStartEndIndex(int[] arr, int elem) {

      int elemIndex = binarySearch(arr, elem, 0, arr.length);

      if(elemIndex == -1)
         System.out.println("-1,-1");

      int lowIndex = elemIndex - 1;
      int highIndex = elemIndex + 1;

      //Find the first index in the lower half of the array

      while(lowIndex >= 0 && (elemIndex = binarySearch(arr, elem, 0, lowIndex)) != -1)
         lowIndex = elemIndex -1;

      //Find the last index in the upper half of the array
      while(highIndex < arr.length && (elemIndex = binarySearch(arr, elem, highIndex, arr.length - 1)) != -1)
         highIndex = elemIndex + 1;

      System.out.println((lowIndex + 1) + ", " + (highIndex -1));

   }

上記のプログラムの時間計算量を見つけるのに苦労しています。以下は私のアプローチです：

私の理解では、最悪のケースはすべての要素が同じ場合{3,3,3,3,3,3} です。最初の出現を見つけるにはコストがかかります:O(logn) //Binary Search

配列の半分 (上下) ごとに、ほとんどの場合 binarySearch を呼び出していO(logn)ます。したがって、全体の複雑さは次のようになりますO(logn ^2)

これは正しい分析ですか？そして、O(logn^2)より良いですO(n)か？

4

3 に答える 3

2 
O(log2n) = O(log2+logn)
Now log2 is a constant. 
So O(log2n) = O(log2+logn) = O(1) + O(logn) = O(logn)

ただし、コードは、指定された整数の出現をバイナリ検索します。<-log(n)
次に、その左端と右端のオカレンスを見つけます。<-log(a)+log(b)最初に出現したのはaとa+b = nです。

したがって、全体の複雑さはO(log(n)+log(a)+log(b)) = O(log(n*a*b)) = O(log(n))

編集：待って！私はあなたのコードを読み違えました。見つけている最初のオカレンスを見つけた後、O(logn) 時間で左端と右端を見つけることができます。

基本的に、出現箇所を見つける最初の部分をスキップして、 O(logn) で実行できます。次のような条件を指定する必要があります。 

while A[i] != q or A[i-1] != A[i]:
    if A[i] < q: low = i + 1
    else: high: = i - 1

ループの終了後i、 の左端のオカレンスになりqます。

while A[i] != q or A[i+1] != A[i]:
    if A[i] > q: high = i - 1
    else: low = i + 1

ループを終了した後i、 の右端のオカレンスになりqます。

どこlowとhighはどこからどこまでのインデックスで、クエリを見つけている場所とi = low+high/2各ステップでのインデックスです。

WARNING :iリストから出ない[0..length of list-1]場合やリストにない場合など、その他のケースを処理する必要がありqます。

どちらの部分にも時間がかかるO(logn)ため、時間の複雑さの合計はどちらO(logn)よりも高速になりますO((logn)^2)

于 2013-07-21T04:53:08.737 に答える
0

私はこのようにプログラムを書きました

int[] secondarr = new int[]{0,0,2,3,3,3,3,4,7,7,9};
    int searchNum = 3;
    int min = -1,max=-1;
    int noOfTimesLoopExecuted = 0;
    for(int ind=0, stop=0;ind<secondarr.length && stop==0;ind++) {
        if(searchNum>=secondarr[ind]){
            if(searchNum==secondarr[ind]){
            if(min==-1){
                min=ind;
            } else {
                max=ind;
            }
            }
        } else {
            stop = 1;
        }
        noOfTimesLoopExecuted = ind;
    }
    System.out.println("start index:"+min+","+"end index:"+max);
    System.out.println("noOfTimesLoopExecuted:"+noOfTimesLoopExecuted);
于 2015-05-28T07:50:58.483 に答える