java - 圆形阵列环路，检测

Question

我正在解决一个问题，并且已经花了一些时间。问题陈述:给你一个正整数和负整数的数组。如果索引处的数字 n 为正，则向前移动 n 步。相反，如果为负数(-n)，则向后移动 n 步。假设数组的第一个元素向前排列在最后一个元素旁边，最后一个元素向后排列在第一个元素旁边。判断这个数组是否存在循环。循环在特定索引处开始和结束，循环中包含超过 1 个元素。循环必须是“向前”或“向后”。

示例 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)。