java循环数组循环，检测

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

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

在这种情况下，当按照数组元素值的指示前进到下一个索引时，将导致达到相同的索引，“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
}

Answer 3

我认为不能保证循环将继续进行到第一个元素，这是错误的吗？因此，您不能只做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?