题目描述：

LeetCode 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?

题目大意：

给定一个整数数组。如果某下标位置的数字n为正数，则向前移动n步。反之，如果是负数，则向后移动-n步。假设数组首尾相接。判断数组中是否存在环。环中至少包含2个元素。环中的元素一律“向前”或者一律“向后”。

满足O(n)时间复杂度和O(1)空间复杂度。

解题思路：

深度优先搜索（DFS Depth First Search）

对nums中的各元素执行DFS，将搜索过的不满足要求的元素置为0，从而避免重复搜索。

当搜索深度depth ＞ 数组长度size时，说明一定有元素被访问了2次，从而推断数组中存在环，返回True。

数组遍历结束，返回False。

由于数组中每一个元素的平均访问次数为常数，因此算法的时间复杂度为O(n)。

例如nums = [7, -1, -2, -3, -1, -2, -3]，0号、3号元素被访问多次，但是各元素的访问次数之和是数组长度的常数倍。

Python代码：

class Solution(object):
    def circularArrayLoop(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        size = len(nums)
        def dfs(idx, cnt):
            if cnt < size:
                nidx = (idx + nums[idx] + size) % size
                if nidx == idx or \
                  nums[nidx] * nums[idx] <= 0 or \
                  dfs(nidx, cnt + 1) == 0:
                    nums[idx] = 0
            return nums[idx]
        for idx in range(size):
            if nums[idx] and dfs(idx, 0):
                return True
        return False

上述解法由于使用了递归，因此空间开销为O(n)。

下面的代码思路同前，采用迭代实现，空间复杂度为O(1)。

Python代码：

class Solution(object):
    def circularArrayLoop(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        size = len(nums)
        next = lambda x : (x + nums[x] + size) % size
        for x in range(size):
            if not nums[x]:
                continue
            y, c = x, 0
            while c < size:
                z = next(y)
                if y == z:
                    nums[y] = 0
                if nums[y] * nums[z] <= 0:
                    break
                y = z
                c += 1
            if c == size:
                return True
            y = x
            while c > 0:
                z = next(y)
                nums[y] = 0
                c -= 1
        return False

 

本文链接：http://bookshadow.com/weblog/2016/11/09/leetcode-circular-array-loop/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码