Минимальный пробел между двумя элементами в заданном массиве

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 и y: два ввода количество массива.

Если minvalue возвращенное n затем x или y нет в массиве.

сложность: O (n), один проход.