圓形陣列環路，檢測

我正在研究一個問題，並花了一些時間在它上面。問題說明：給出了一組正整數和負整數。如果指數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

圓形陣列環路，檢測

回答

相關問題