给定数组中2个元素之间的最小距离

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

Answer 2

基本上，我认为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; 
} 

Answer 3

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 and y：两个输入数组的数量。

如果返回minvalue是n然后x或y不存在于阵列。

复杂性：O（n），一遍。