457. 环形数组循环

亦凉 2021-09-18 13:36 330阅读 0赞

# **问题** #

## 问题描述 ##

给定一组含有正整数和负整数的数组。如果某个索引中的 n 是正数的，则向前移动 n 个索引。相反，如果是负数(-n)，则向后移动 n 个索引。  
假设数组首尾相接。判断数组中是否有环。环中至少包含 2 个元素。环中的元素一律“向前”或者一律“向后”。  
你能写出时间复杂度为 O(n) 且空间复杂度为 O(1) 的算法吗？

## 示例 ##

1.  给定数组 \[2, -1, 1, 2, 2\], 有一个循环，从索引 0 -> 2 -> 3 -> 0。
2.  给定数组\[-1, 2\], 没有循环。

## 注意 ##

给定数组保证不包含元素"0"。

--------------------

# **解答** #

此题若是没有时间和空间复杂度的限制的话是非常简单的。但是想要达到O(n)时间复杂度和O(1)空间复杂度就比较困难，看了别人写的一些博客，还没有看到同时达到上述两个要求的。

通过思考可以知道，想要在一边循环中得到答案同时又保证O(1)的复杂度就要充分利用输入的列表nums。对于nums的每个值我们至少要能获得以下三个信息：

1.  是否是搜索过的
2.  是否是正在搜索的
3.  是否还未搜索

由于0保证不包含在列表中，所以可以用0作为已经搜索过且不存在环的标志；在最开始先求出列表中绝对值最大的数k，再将每个正整数加k，每个负整数减k，这样不在-k到k中的就可以作为还未搜索的标志；反之就是正在搜索的。

解决了这个问题之后，还有一个关键的问题。当某一次搜索失败时，如何将这一次搜索过的元素改为0。如果通过遍历就会导致时间复杂度提高，显然不可以通过这样粗暴的方式。于是便想到了指针的思想，当搜索时，每一个搜索位置都存储上一个搜索的位置信息，这样当搜索失败时，就可以沿着此信息将所有此次搜索的元素全部改为0。具体细节请参考以下代码：

class Solution(object):
        def circularArrayLoop(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            k = len(nums)
            if k > 1:
                l = max([abs(max(nums)), abs(min(nums))])
                for i in range(k):
                    if nums[i] > 0 :
                        nums[i] += l
                    else:
                        nums[i] -= l
                for i in range(k):
                    if nums[i] > l and (nums[i] - l) % k != 0:
                        a = (nums[i] - l + i) % k  #下一位置的索引
                        b = i                      #当前位置索引
                        nums[i] = -1
                        while nums[a] > l and (nums[a] - l) % k != 0:
                            c = nums[a]
                            nums[a] = b
                            b = a
                            a = (a + c - l) % k
                        if 0 < nums[a] <= l or nums[a] == -1:
                            return True
                        else:
                            while nums[b] != -1:
                                a = nums[b]
                                nums[b] = 0
                                b = a
                            nums[b] = 0
                    elif nums[i] < -l and (nums[i] + l) % k != 0:
                        a = (i + nums[i] + l) % k  #下一位置的索引
                        b = i                      #当前位置索引
                        nums[i] = 1
                        while nums[a] < -l and (nums[a] + l) % k != 0:
                            c = nums[a]
                            nums[a] = b
                            b = a
                            a = (a + c + l) % k
                        if 0 < nums[a] <= l or nums[a] == 1:
                            return True
                        else:
                            while nums[b] != 1:
                                a = nums[b]
                                nums[b] = 0
                                b = a
                            nums[b] = 0
            return False