c - 给定数组中两个元素之间的最小距离

Question

在竞赛中，他们要求编写一个 C 函数，返回给定数组中 X 和 Y 之间的最小距离，其中 X 和 Y 是数组的元素，前提是 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) 时间复杂度一样]？

Answer 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;
}