457. Circular Array Loop

缺乏、安全感 2022-02-03 15:34 208阅读 0赞

You are given a circular array nums of positive and negative integers. If a number k at an index is positive, then move forward k steps. Conversely, if it's negative (-k), move backward k steps. Since the array is circular, you may assume that the last element's next element is the first element, and the first element's previous element is the last element.
    
    Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle's length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.
    
     
    
    Example 1:
    
    Input: [2,-1,1,2,2]
    Output: true
    Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.
    Example 2:
    
    Input: [-1,2]
    Output: false
    Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.
    Example 3:
    
    Input: [-2,1,-1,-2,-2]
    Output: false
    Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.
     
    
    Note:
    
    -1000 ≤ nums[i] ≤ 1000
    nums[i] ≠ 0
    1 ≤ nums.length ≤ 5000
     
    
    Follow up:
    
    Could you solve it in O(n) time complexity and O(1) extra space complexity?

要解决这题，首先要明白一个点，如果数组内所有数全部为同号，则必定存在循环。所以可以用两个指针，一个快一个慢来解决这个问题。

public boolean circularArrayLoop(int[] nums) {
            int n = nums.length;
            if(n == 1) return false;
            for(int i = 0; i < n; ++i) {
                if(nums[i] == 0)
                    continue;
                int j = i, k = getIndex(j, nums);//两个指针，一个快，一个慢
                while(nums[k] * nums[i] > 0 && nums[getIndex(k, nums)] * nums[i] > 0) {
                    if(j == k) {//如果有一个循环，则必定会有j等于k
                        if(j == getIndex(k, nums))//排除[1]和[-1]和nums[j]=0的可能
                            break;
                        return true;
                    }
                    j = getIndex(j, nums);//移动一次
                    k = getIndex(getIndex(k, nums), nums);//移动两次
                }
                j = i;//将从i开始的路径上的数置零，表示在该点上没有循环
                while(nums[j] * nums[i] > 0) {
                    int next = getIndex(j, nums);
                    nums[j] = 0;
                    j = next;
                }
            }
            return false;
        }
    
        private int getIndex(int i, int[] nums) {
            int n = nums.length;
            return i + nums[i] >= 0? (i + nums[i]) % n: n + ((i + nums[i]) % n);
        }