Как вы удаляете цикл целых чисел (например, 1-2-3-1) из массива

Question

Если у вас есть массив целых чисел, например 1 2 5 4 3 2 1 5 9 Что является лучшим способом в C, чтобы удалить циклы целых чисел из массива. то есть выше, 1-2-5-4-3-2-1 является циклом и должно быть удалено, чтобы оставить только 1 5 9.

Как я могу это сделать? Спасибо !!

Answer 1

Прямой поиск в массиве может выглядеть так:

int arr[] = {1, 2, 5, 4, 3, 2, 1, 5, 9};
int len = 9;
int i, j;

for (i = 0; i < len; i++) {
   for (j = 0; j < i; j++) {
      if (arr[i] == arr[j]) {
         // remove elements between i and j
         memmove(&arr[j], &arr[i], (len-i)*sizeof(int));
         len -= i-j;
         i = j;
         break;
      }
   }
}

Answer 2

Существует простой способ со сложностью O (n ^ 2): просто итерируйте по каждой записи массива с самого начала и ищите в массиве последнее идентичное значение. Если он находится в той же позиции, что и ваша текущая позиция, двигайтесь дальше. В противном случае удалите последовательность (кроме начального значения) и продолжайте. Вы должны быть в состоянии реализовать это, используя два вложенных цикла for и условный memcpy.

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

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

2) Выполните итерацию один раз над отсортированным массивом (O (n)), ища прогоны с тем же значением. Поскольку эти прогоны сами сортируются по положению, вы можете тривиально найти каждый цикл, включающий это значение, сравнивая соседние пары на равенство. Сотрите (не удалите) каждый цикл из исходного массива, заменив каждое значение, кроме последнего, на часовой (нулевой может работать). Пока не закрывайте пробелы, иначе ссылки разорвутся.

NB. На этом этапе вам необходимо игнорировать любые конечные точки, которые уже были удалены из массива. Поскольку они разрешаются для дозорных, вы просто должны быть осторожны, чтобы не стереть «прогоны», связанные со значением дозорного с обоих концов.

3) Удалите отсортированный массив и используйте часовые, чтобы закрыть пробелы в исходном массиве. Это должно быть O (n).

Фактически реализация этого на любом данном языке оставлена ​​как упражнение для читателя. : -)

Answer 3

Построить график и выбрать ребра, исходя из глубины поиска, сначала по нему.

Помечайте вершины при их посещении, добавляйте ребра при прохождении графа, не добавляйте ребра, которые уже были выбраны - они соединят ранее посещенные компоненты и, следовательно, создадут цикл.

Из массива в вашем примере мы не можем сказать, что считать циклом.

В вашем примере 2 -> 5 и 1 -> 5, а также 1 -> 2, поэтому на графике (?):

1 -> 2
|    |
|    V
+--> 5

Так где же информация о том, какие элементы связаны?