1

コンテストで、彼らは与えられた配列の X と Y の間の最小距離を返す C 関数を書くように依頼しました。ここで、X と Y は配列の要素です。

コードを書いたが、そのコードが多くifの とに遭遇したelse場合、

私のコード（いくつかのバグがあります）：

 int getMinXYDist(int arr[],int n,int x,int y){
         int i,flag = 0,ele = -1 ,dist = 0;
         int minDist = 1000; // SETTING minDist TO MAX VALUE.
         for( i = 0 ; i< n; i++)
          if(arr[i] == x || arr[i] == y){
           if(flag == 0){
            flag = 1;
            ele = arr[i]==x?x:y;
            dist = 0;
          }
        else{
          if(ele == x ){
           if(arr[i] == y){
                minDist = dist < minDist ? dist : minDist;
                dist = 0;
                ele = y;
           }
           else //if(arr[i] == x){
               dist = 0;
          }
          else { //if(ele == y)
              if(arr[i] == x){
                minDist = dist < minDist ? dist : minDist;
                dist = 0;
                ele = x;
           }
          }

          }
        }
          else {
              if(flag == 1)
            dist++;
          }

   return minDist;
}

 void main(){
      int arr = {6,1,5,1,8,6,3,4};
      printf("\n%d" ,getMinXYDist(arr,sizeof(arr)/sizeof(int),6,5) ); //Must return 2.
 }

[O(n)時間の複雑さのように]距離を計算するよりスマートな方法を提案できる人はいますか?

4

3 に答える 3

1

x または y が見つかった場合は、見つかったインデックスを記録します。両方が見つかったら、いずれかを見つけるたびに、もう一方の値を含む最後のインデックスまでの距離を計算します。距離が以前の最小値よりも小さい場合は、最小値を更新します。

int getMinXYDist(int arr[],int n,int x,int y)
{
    int i, indexX, indexY;
    int foundX = 0;
    int foundY = 0;
    int curDist;
    int minDist = n;

    for (i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            foundX = 1;
            indexX = i;
            if (foundX && foundY)
            {
                curDist = indexX - indexY;
                if (curDist < minDist)
                {
                    minDist = curDist;
                }
            }
        }
        else if (arr[i] == y)
        {
            foundY = 1;
            indexY = i;
            if (foundX && foundY)
            {
                curDist = indexY - indexX;
                if (curDist < minDist)
                {
                    minDist = curDist;
                }
            }
        }
    }
    return minDist;
}
于 2013-04-10T20:07:01.000 に答える
0

基本的に、OP のソリューションはすでに最適であると思います。このアルゴリズムの下限はnステップです。つまり、1 回の反復で実行されます。

// if -1 is returned, then none of x and y are in the array
// if n is returned, then one of x and y is not in the array
// otherwise, mindist(x, y) is returned.
int test(int v[], int n, int x, int y)
{
    int flag = -1;
    int i, a = -1, b = -1, dist = n;
    for (i = 0; i < n; ++i) {
        if (v[i] == x) {
            flag = 0;
            a = i;
            break;
        } else if (v[i] == y) {
            flag = 1;
            b = i;
            break;
        }
    }
    if (flag < 0) return -1; // x and y are both not in array;

    for (++i; i < n; ++i) {
        if (v[i] == x) {
            if (0 == flag) a = i;
            else {
                flag = 0;
                if (i - b < dist) dist = i - b;
                a = i;
            }
        } else if (v[i] == y) {
            if (1 == flag) b = i;
            else {
                flag = 1;
                if (i - a < dist) dist = i - a;
                b = i;
            }
        }
    }

    return dist;
}
于 2013-04-10T20:12:48.067 に答える