循环数组循环检测

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]);

}

- user754036

---

如果数组中没有出现0，那么在什么情况下可能没有循环呢？（如果方法只包含“return true;”，那么它算作O(0)吗？） - Dawood ibn Kareem

你可以在循环中计数直到大小。当计数等于大小时停止循环。 - Suresh A

我的理解是：没有循环实际上意味着“只有一个元素的循环”=> 当一个元素指向它自己时，这就是@Surace所说的。 - alexbt

循环必须是正向或反向的。这是问题的一部分还是只是一种假设？ - Dolev

Answer 1

这可以看作是在有向（可能是不连通的）图中寻找循环检测的一种版本，或者更像是在给定图中为所有连接的子图找到最小生成树。数组中的数字是顶点，基于顶点值之间形成边缘。目前没有已知的图解析算法可以在O(1)空间复杂度下解决此问题。由于最佳图解析算法可以在O(V+E)时间内解决，而在本例中V=E，因此在某些情况下可以用O(n)时间复杂度解决。目前最好的算法是Kruskal算法：http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/，其在O(nlogn)时间内解决。

- Phanindra Kumar Kannaji

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;

这与通常使用链表提出的问题非常相似：如何检测链表中的循环？

- alexbt

---

我认为这并不能完全解决问题，因为循环需要大于单个元素。例如2：给定数组[-1, 2]，没有循环。另外，由于数组被称为循环的，所以没有“结束”：var1到达末尾。 - dting

这是我的看法：“……在循环中以特定索引结束，且有多于1个元素”。因此，当当前索引指向自身时，即为结束，这是我的理解。所以对于[-1, 2]，当var1到达索引[1]时，它的下一个元素是它本身，因此“结束已到达”。你说得对，“只有1个元素的数组”确实是需要在进入逻辑之前处理的特殊情况。 - alexbt

Answer 3

由于保证没有值为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
}

- dting

---

我该如何使用两个变量？它们应该如何向前或向后移动？有两个选项，如果元素值为正，则索引向前移动，否则向后移动。在某些时候，索引将被重置为0或size-1。 - user754036

这与如何找出下一个索引有关。http://stackoverflow.com/a/22264961/635411 - dting