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

Question

У меня есть массив из двойных значений 'N', но я пытаюсь найти пару одинаковых элементов, которые имеют наибольшее расстояние между ними.

Так, в качестве примера;

{1, 3, 5, 3, 7, 9, 10, 5, 6, 7, 1}
Output: (1,1) has the largest distance between them 

У кого-нибудь есть какие-либо идеи о том, как я к этому подхожу, потому что я совершенно тупой?

Заранее спасибо!

Answer 1

Код может пробовать каждую пару.

И все же ключ заключается в том, чтобы избежать тестирования пар, которые меньше текущего известного максимального расстояния.

size_t max_common_element_distance(size_t n, const double *x) {
  size_t max_distance = 0;
  for (size_t i = 0; i < n; i++) {
    for (size_t j = i+1; j + max_distance < n; j++) {
      // test beyond the max distance for a better one.
      if (x[i] == x[j + max_distance]) {
        max_distance = j + max_distance - i;
        // Perhaps record other info here, like the index of the 2 elements 
        // to use as part of the "Output: ..." report
      }
    }
  }
  return max_distance;
}

Лучший код будет запускать j l oop в обратном направлении, от n-max_distance-1 до t i+1. Но звучит так, будто OP нуждается в хорошей, не такой сложной, отправной точке.

---

Глубже: порядок сложности выше O(n*n). Решение O(n*log(n)) существует путем формирования списка пар (значение, индекс), сортировки его по значению (а затем по индексу по связям), затем один раз обходит список, чтобы найти максимальную разницу индекса.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  double value;
  size_t index;
} pair;

int pair_cmp(const void *a, const void *b) {
  const pair *pa = a;
  const pair *pb = b;
  int cmp = (pa->value > pb->value) - (pa->value < pb->value);
  if (cmp == 0) {
    cmp = (pa->index > pb->index) - (pa->index < pb->index);
  }
  return cmp;
}

size_t max_common_element_distance(size_t n, const double *x) {
  size_t max_distance = 0;
  if (n > 0) {
    pair y[n];
    for (size_t i = 0; i < n; i++) {
      y[i].index = i;
      y[i].value = x[i];
    }
    qsort(y, n, sizeof y[0], pair_cmp);
    size_t from, to;
    size_t first = 0;
    for (size_t i = 1; i < n; i++) {
      if (y[i].value == y[first].value) {
        size_t distance = y[i].index - y[first].index;
        if (distance > max_distance) {
          max_distance = distance;
          from = y[first].index;
          to = y[i].index;
        }
      } else {
        first = i;
      }
    }
    if (max_distance > 0) {
      printf("from:%zu to:%zu dist:%zu val:%g\n", from, to, max_distance, x[from]);
    }
  }
  return max_distance;
}

int main() {
  double val[] = {1, 3, 5, 3, 7, 9, 10, 5, 6, 7, 1};
  size_t n = sizeof val/ sizeof val[0];
  max_common_element_distance(n, val);
}

Выход

from:0 to:10 dist:10 val:1

Answer 2

Вот мои пять центов. :)

#include <stdio.h>

int main(void) 
{
    int a[] = { 1, 3, 5, 3, 7, 9, 10, 5, 6, 7, 1 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t first = 0, last = 0;

    for ( size_t i = 0; i < N - ( last - first ); i++ )
    {
        size_t j = N;
        while ( --j != i && a[j] != a[i] );

        if ( j != i )
        {
            if ( last - first < j - i )
            {
                first = i;
                last = j;
            }
        }
    }

    if ( first != last )
    {
        printf( "%d: ( %zu, %zu )\n", a[first], first, last );
    }

    return 0;
}

Вывод программы:

1: ( 0, 10 )

Циклы могут быть более оптимизированы, если включить следующее условие

    if ( i == 0 || a[i] != a[last] )

для пропуска уже рассмотренных значений.

Вот программа с этим оператором if.

#include <stdio.h>

int main(void) 
{
    int a[] = { 1, 3, 5, 3, 7, 9, 10, 5, 6, 7, 1 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t first = 0, last = 0;

    for ( size_t i = 0; i < N - ( last - first ); i++ )
    {
        if ( i == 0 || a[i] != a[last] )
        {
            size_t j = N;
            while ( --j != i && a[j] != a[i] );

            if ( j != i )
            {
                if ( last - first < j - i )
                {
                    first = i;
                    last = j;
                }
            }
        }           
    }

    if ( first != last )
    {
        printf( "%d: ( %zu, %zu )\n", a[first], first, last );
    }

    return 0;
}

Вот та же программа, в которую вставлен тестовый вывод для отображения как часто выполняется внутреннее l oop.

#include <stdio.h>

int main(void) 
{
    int a[] = { 1, 1, 1, 1, 2, 2, 2, 2, 2, 3 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t first = 0, last = 0;

    for ( size_t i = 0; i < N - ( last - first ); i++ )
    {
        if ( i == 0 || a[i] != a[last] )
        {
            printf( "Inner loop for %d\n", a[i] );

            size_t j = N;
            while ( --j != i && a[j] != a[i] );

            if ( j != i )
            {
                if ( last - first < j - i )
                {
                    first = i;
                    last = j;
                }
            }
        }           
    }

    if ( first != last )
    {
        printf( "%d: ( %zu, %zu )\n", a[first], first, last );
    }

    return 0;
}

Выход программы:

Inner loop for 1
Inner loop for 2
2: ( 4, 8 )

Таким образом, внутреннее l oop выполняется только два раза.