圆形阵列环路，检测

我正在研究一个问题，并花了一些时间在它上面。问题说明：给出了一组正整数和负整数。如果指数n是正数，则前进n步。相反，如果它是负数（-n），则向后移动n步。假设数组的第一个元素在最后一个元素旁边转发，最后一个元素在第一个元素后面。确定此数组中是否存在循环。循环开始并结束于循环中具有多于一个元素的特定索引处。示例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]); 

}

来源

2016-11-16 user754036

在什么情况下可能没有循环，如果数组中没有0？（如果方法只包含'return true;'，它会计为O（0））吗？ –

你可以计算循环，直到大小。并停止循环，当计数等于大小 –

我的理解：没有循环真的意味着“循环只有一个元素”=>当一个元素指向自己，哪个下降@Surace说。 – alexbt

我错了，认为不能保证循环将继续与第一个元素？因此，你不能只是做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?

来源

2016-11-16 03:30:19 alexbt

我不认为这完全解决了问题，因为循环要求比单个元素大。 '例2：给定数组[-1，2]，没有循环.'也没有“结束”，因为该数组被称为是循环的：'var1到达结尾' – DTing

这里是我对此的看法：“ ...在循环中具有多于一个元素的特定索引处结束“。所以最后是当前指数指向自己的时候，这是我的理解。所以在[-1,2]中，当var1到达索引[1]时，它的下一个元素就是它自己，所以“到达结束”。你是对的“1元素数组”确实是一个特殊情况，需要在进入逻辑之前处理 – alexbt

，因为有担保值为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 
}

来源

2016-11-16 04:13:38 DTing

我怎样才能使用两个变量？他们应该如何前进或后退？有两个选项，如果元素值为+ ve，则索引向前移动，否则向后移动。在某个时候，索引将被重置为0或大小为1。 – user754036

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

这可以被看作是在一个有向（可能断开）图形或更像找到最小生成树在给定图中的所有连接的子图的一个版本周期检测的。数组中的数字是顶点，并且基于顶点值将在顶点之间形成边。没有已知的图解析算法可以解决O（1）空间复杂度问题。这可以通过O（n）时间复杂度来解决，因为在这种情况下可以在O（V + E）时间和V = E中解决最佳图解析算法，这使得可以在一些情况下用O案例。最着名的算法是Kruskal's：http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/，它在O（nlogn）时间内求解。

来源

2017-03-05 20:20:47

圆形阵列环路，检测

回答

相关问题