Circular Array Loop, обнаружение

Question

Я работаю над проблемой и потратил на нее некоторое время. Заявление об ошибке: Вам предоставляется массив положительных и отрицательных целых чисел. Если число n в индексе положительное, переместите n шагов. И наоборот, если он отрицательный (-n), двигайте назад n шагов. Предположим, что первый элемент массива находится вперед рядом с последним элементом, а последний элемент находится назад рядом с первым элементом. Определите, существует ли цикл в этом массиве. Цикл начинается и заканчивается с определенным индексом с более чем 1 элементом вдоль цикла. Цикл должен быть «вперед» или «назад».

Пример 1: Учитывая массив [2, -1, 1, 2, 2], существует петля из индекса 0 -> 2 -> 3 - > 0.

Пример 2: Учитывая массив [-1, 2], нет петли

. Примечание: данный массив гарантированно не содержит ни одного элемента "0"

Можете ли вы. сделать это в O (n) сложности времени и O (1) сложности пространства?

И это мое решение в процессе, однако, я не уверен, как мне d условие do-while, когда нет обнаруженного цикла. Я считаю, что мой код будет работать бесконечно, если не обнаружено никакого цикла.

public static boolean circularArrayLoop(int[] nums) { 
    int size = nums.length; 
    if(size < 2) return false; 

    int loopStart = nums[0]; 
    int index = 0; 
    int start = nums[0]; 
    do{ 
     if(nums[index] > 0){ 
      index = moveForward(index, nums[index], size); 
     }else { 
      index = moveBackward(index, Math.abs(nums[index]), size); 
     } 

    }while (loopStart != nums[index]); 

} 

Answer 1

Неужели я не считаю, что нет гарантии, что цикл будет продолжаться с первым элементом? Таким образом, вы не можете просто сделать int loopStart = nums[0];

• Что делать, если ваш пример 1 был довольно [2, -1, 1, 4, 2], то цикл будет из индекса 0 -> 2 -> 3 -> 2. И ваш чек с помощью loopstart не будет работать, поскольку он проверяет sums[0].

Хорошим решением является использование 2 переменных и их перемещение с разной скоростью (в два раза быстрее). Если массив/связанный список является круговым, вы попадаете в точку, где var1 равно var2.

Вот псевдокод:

if array.length<=1 
    return false 

int i=0; 

//loop is when "var1 == var2" 
//end is when "var1 == abs(array.length)" 
loop (until var1 == var2 or var1 reaches the end) 

    var1 = moveToNext(var1) 
    if (i++ % 2 == 0) 
     var2 = moveToNext(var2) 

return var1 == var2; 

Это очень похоже на вопрос, как правило, спросил с использованием связанного списка: How to detect a loop in a linked list?

Answer 2

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

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

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

public static void main(String[] args) { 
    int[] loop = {2, -1, 1, 2, 2}; 
    int[] noloop = {-1, 2}; 
    System.out.println(circularArrayLoop(loop)); 
    System.out.println(circularArrayLoop(noloop)); 
} 

static int nextIndex(int[] nums, int cur) { 
    // Get next index based on value taking into account wrapping around 
} 

static boolean circularArrayLoop(int[] nums) { 
    int fast = 0; 
    int slow = 0; 
    do { 
     // advance fast cursor twice 
     // advance slow cursor once 
    } while (fast != slow); 
    int next = nextIndex(nums, fast); 
    // return if the loop has more than a single element 
} 

Answer 3

Это можно рассматривать как вариант обнаружения цикла в ориентированном (возможно, отключенном) графе или более, как нахождение минимального остовного дерева для всех подключенных подграфов в данной графе. Числа в массиве - это вершины, и ребро будет образовываться между вершинами на основе значения вершины. Нет известных алгоритмов синтаксического анализа, которые могут решить его в сложности O (1).Это может быть решено в O (n) временной сложности, так как лучшие алгоритмы синтаксического анализа могут быть решены в O (V + E) времени и V = E в этом случае, что позволяет решить с O (n) временную сложность в некоторых случаев. Наиболее известным алгоритмом является Kruskal's: http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/, который решает в O (nlogn) время.