1

在一次比赛中，他们要求编写一个 C 函数，该函数返回给定数组中 X 和 Y 之间的最小距离，其中 X 和 Y 是数组的元素，前提是 X 和 Y 是不同的。

如果已经写了一段代码，但是那段代码遇到了很多if's 和else's，

我的代码（有一些错误）：

 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

If x or y is found, record the index it was found at. Once both have been found, each time you find either, compute distance to the last index containing the other value. Update the minimum value if the distance is lower than the previous minimum.

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步骤，即一次迭代完成。

// 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 回答
0 
int minDistance ( int arr[], int n, int x, int y) {

    if(x == y) return 0;
    int index1 = -1;
    int index2 = -1;
    int minvalue = n;

    for(int i = 0 ; i < n; i++){
        if((arr[i] == x) && ((i-index2) < minvalue)){
              index1 = i;                                    
              if( index2 != -1)minvalue = i-index2;
        }else if((arr[i] == y) && ((i-index1) < minvalue)){
              index2 = i;                                    
              if( index1 != -1)minvalue = i-index1;
        }     
    }
    return minvalue;
}

在哪里

  • n: 数组的大小。
  • x和y：两个输入数组的数量。

如果minvalue返回，n则数组中不存在x或y不存在。

复杂性：O(n)，一次通过。

于 2013-07-30T19:29:21.637 回答