Цикл в циклическом массиве

Цикл в циклическом массиве

Условие задачи

Дан массив положительных и отрицательных чисел. Если в некоторой позиции записано число m, то при положительном m нужно переместиться на m индексов вперёд, а при отрицательном — на m индексов назад. Массив считается циклическим: после последнего элемента движение вперёд продолжается с первого, а перед первым элементом движение назад продолжается с последнего.

Определите, существует ли в массиве цикл. Цикл должен содержать больше одного элемента и сохранять одно направление: в нём не могут одновременно встречаться движения вперёд и назад.

Пример 1:

1
2

Вход:  [1, 2, -1, 2, 2]
Выход: true

Цикл проходит по индексам 0 -> 1 -> 3 -> 0.

Пример 2:

1
2

Вход:  [2, 2, -1, 2]
Выход: true

Цикл проходит по индексам 1 -> 3 -> 1.

Пример 3:

1
2

Вход:  [2, 1, -1, -2]
Выход: false

Решение

Запустим быстрый и медленный указатели из каждого индекса массива. Для каждого запуска запомним направление начального элемента. При вычислении следующего индекса остановим поиск в двух случаях:

  1. Направление движения изменилось.
  2. Следующий индекс совпал с текущим, то есть найден недопустимый цикл из одного элемента.

Если оба указателя встретились и ни одно из этих условий не сработало, найден допустимый цикл.

Код

Вот как будет выглядеть наш алгоритм:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

package main

import "fmt"

func loopExists(numbers []int) bool {
	for start := range numbers {
		forward := numbers[start] >= 0
		slow, fast := start, start

		for {
			slow = nextIndex(numbers, forward, slow)
			fast = nextIndex(numbers, forward, fast)
			if fast != -1 {
				fast = nextIndex(numbers, forward, fast)
			}

			if slow == -1 || fast == -1 || slow == fast {
				break
			}
		}

		if slow != -1 && slow == fast {
			return true
		}
	}

	return false
}

func nextIndex(numbers []int, forward bool, current int) int {
	currentDirection := numbers[current] >= 0
	if currentDirection != forward {
		return -1
	}

	next := (current + numbers[current]) % len(numbers)
	if next < 0 {
		next += len(numbers)
	}

	if next == current {
		return -1
	}

	return next
}

func main() {
	fmt.Println(loopExists([]int{1, 2, -1, 2, 2}))
	fmt.Println(loopExists([]int{2, 2, -1, 2}))
	fmt.Println(loopExists([]int{2, 1, -1, -2}))
}

Вывод:

1
2
3

true
true
false

Временная сложность

Для каждого из \(N\) начальных индексов поиск цикла может пройти до \(N\) элементов. Поэтому временная сложность равна \(O(N^2)\).

Пространственная сложность

Алгоритм использует постоянный объём дополнительной памяти, поэтому пространственная сложность равна \(O(1)\).

Альтернативный подход

Если запоминать все уже проверенные индексы в отдельном массиве, каждый элемент потребуется исследовать только один раз. Временная сложность уменьшится до \(O(N)\), а пространственная возрастёт до \(O(N)\).