457. Circular Array Loop

457. Circular Array Loop

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it’s negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be “forward” or “backward’.

Example 1: Given the array [2, -1, 1, 2, 2], there is a loop, from index 0 -> 2 -> 3 -> 0.

Example 2: Given the array [-1, 2], there is no loop.

Note: The given array is guaranteed to contain no element “0”.

Can you do it in O(n) time complexity and O(1) space complexity?

class Solution { int[] arr; public boolean circularArrayLoop(int[] nums) { arr = nums; for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) continue; //two pointers int j = i, k = i; while (nums[i] * nums[shift(k)] > 0 && nums[i] * nums[shift(shift(k))] > 0) { j = shift(j); k = shift(shift(k)); if (j == k) { // check for loop with only one element if (j == shift(j)) break; return true; } } // loop not found, set all element along the way to 0， not necessary } return false; } public int shift(int pos) { return ( pos + arr[pos] + arr.length ) % arr.length; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。