循环数组循环，检测

Question

我正在解决一个问题，并且已经花了一些时间。问题陈述:给你一个正整数和负整数的数组。如果索引处的数字n为正，则向前移动n步。相反，如果它是负的(-n)，则向后移动n步。假设数组的第一个元素在最后一个元素的前面，最后一个元素在第一个元素的后面。确定此数组中是否存在循环。一个循环在一个特定的索引处开始和结束，沿着循环有一个以上的元素。循环必须是“向前”或“向后”。

示例1:给定数组2，-1，1，2，2，有一个循环，从索引0 -> 2 -> 3 -> 0开始。

示例2:给定数组-1，2，没有循环。

注意:给定的数组保证不包含元素"0“。

你能做到O(n)时间复杂度和O(1)空间复杂度吗？

这是我正在进行的解决方案，但是，当没有检测到循环时，我不确定应该如何结束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

这可以看作是有向图(可能是断开的)图中的循环检测版本，或者更像是为给定图中的所有连通子图找到最小生成树。数组中的数字是顶点，将根据顶点值在顶点之间形成一条边。目前还没有已知的图解析算法可以在O(1)的空间复杂度内解决这个问题。这个问题可以在O(n)时间复杂度内解决，因为在这种情况下，最好的图解析算法可以在O(V+E)时间和V=E时间内解决，这使得在某些情况下可以解决O(n)时间复杂度。最著名的算法是Kruskal的：http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/，它在O(nlogn)时间内求解。

Answer 2

我认为不能保证循环将从第一个元素继续下去，这是错误的吗？因此，您不能只使用int loopStart = nums[0];

如果你的例子1是[2, -1, 1, 4, 2]，那么循环应该是来自索引0 -> 2 -> 3 -> 2。而且，您使用loopstart进行的检查不会起作用，因为它会检查sums[0]。

一个好的解决方案是使用两个变量，并以不同的速度移动它们(一个是速度的两倍)。如果数组/链表是循环的，那么您将达到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 3

因为保证没有值为0的元素，所以总是会有一个循环。限定符is循环必须大于单个元素长度。

在这种情况下，当按照数组元素值的指示前进到下一个索引时，会达到相同的索引，则会出现"no“循环。

快速和缓慢移动的光标可以用来查找循环的开始。然后，将单个游标向前移动，直到它返回到相同的索引，您就可以遍历循环的元素。如果单次前进将游标返回到相同的索引，则不会出现循环。

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
}