457. 環(huán)形數(shù)組循環(huán)

RaoMeng 發(fā)布于2019-07-30 18:38 / 824人閱讀

摘要：問題問題描述給定一組含有正整數(shù)和負(fù)整數(shù)的數(shù)組。假設(shè)數(shù)組首尾相接。判斷數(shù)組中是否有環(huán)。你能寫出時(shí)間復(fù)雜度為且空間復(fù)雜度為的算法嗎示例給定數(shù)組有一個(gè)循環(huán)，從索引。給定數(shù)組沒有循環(huán)。注意給定數(shù)組保證不包含元素。

問題 問題描述

給定一組含有正整數(shù)和負(fù)整數(shù)的數(shù)組。如果某個(gè)索引中的 n 是正數(shù)的，則向前移動(dòng) n 個(gè)索引。相反，如果是負(fù)數(shù)(-n)，則向后移動(dòng) n 個(gè)索引。
假設(shè)數(shù)組首尾相接。判斷數(shù)組中是否有環(huán)。環(huán)中至少包含 2 個(gè)元素。環(huán)中的元素一律“向前”或者一律“向后”。
你能寫出時(shí)間復(fù)雜度為 O(n) 且空間復(fù)雜度為 O(1) 的算法嗎？

示例

給定數(shù)組 [2, -1, 1, 2, 2], 有一個(gè)循環(huán)，從索引 0 -> 2 -> 3 -> 0。

給定數(shù)組[-1, 2], 沒有循環(huán)。

注意

給定數(shù)組保證不包含元素"0"。

解答

此題若是沒有時(shí)間和空間復(fù)雜度的限制的話是非常簡單的。但是想要達(dá)到O(n)時(shí)間復(fù)雜度和O(1)空間復(fù)雜度就比較困難，看了別人寫的一些博客，還沒有看到同時(shí)達(dá)到上述兩個(gè)要求的。

通過思考可以知道，想要在一邊循環(huán)中得到答案同時(shí)又保證O(1)的復(fù)雜度就要充分利用輸入的列表nums。對(duì)于nums的每個(gè)值我們至少要能獲得以下三個(gè)信息：

是否是搜索過的

是否是正在搜索的

是否還未搜索

由于0保證不包含在列表中，所以可以用0作為已經(jīng)搜索過且不存在環(huán)的標(biāo)志；在最開始先求出列表中絕對(duì)值最大的數(shù)k，再將每個(gè)正整數(shù)加k，每個(gè)負(fù)整數(shù)減k，這樣不在-k到k中的就可以作為還未搜索的標(biāo)志；反之就是正在搜索的。

解決了這個(gè)問題之后，還有一個(gè)關(guān)鍵的問題。當(dāng)某一次搜索失敗時(shí)，如何將這一次搜索過的元素改為0。如果通過遍歷就會(huì)導(dǎo)致時(shí)間復(fù)雜度提高，顯然不可以通過這樣粗暴的方式。于是便想到了指針的思想，當(dāng)搜索時(shí)，每一個(gè)搜索位置都存儲(chǔ)上一個(gè)搜索的位置信息，這樣當(dāng)搜索失敗時(shí)，就可以沿著此信息將所有此次搜索的元素全部改為0。具體細(xì)節(jié)請(qǐng)參考以下代碼：

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                      #當(dāng)前位置索引
                    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                      #當(dāng)前位置索引
                    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