資訊專欄INFORMATION COLUMN
摘要：問題問題描述給定一組含有正整數和負整數的數組。假設數組首尾相接。判斷數組中是否有環。你能寫出時間復雜度為且空間復雜度為的算法嗎示例給定數組有一個循環，從索引。給定數組沒有循環。注意給定數組保證不包含元素。
問題 問題描述
給定一組含有正整數和負整數的數組。如果某個索引中的 n 是正數的，則向前移動 n 個索引。相反，如果是負數(-n)，則向后移動 n 個索引。
假設數組首尾相接。判斷數組中是否有環。環中至少包含 2 個元素。環中的元素一律“向前”或者一律“向后”。
你能寫出時間復雜度為 O(n) 且空間復雜度為 O(1) 的算法嗎？
給定數組 [2, -1, 1, 2, 2], 有一個循環，從索引 0 -> 2 -> 3 -> 0。
給定數組[-1, 2], 沒有循環。
注意給定數組保證不包含元素"0"。
此題若是沒有時間和空間復雜度的限制的話是非常簡單的。但是想要達到O(n)時間復雜度和O(1)空間復雜度就比較困難，看了別人寫的一些博客，還沒有看到同時達到上述兩個要求的。
通過思考可以知道，想要在一邊循環中得到答案同時又保證O(1)的復雜度就要充分利用輸入的列表nums。對于nums的每個值我們至少要能獲得以下三個信息：
是否是搜索過的
是否是正在搜索的
是否還未搜索
由于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
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/42786.html
摘要：既然說到地址空間了就順帶說一下上面環形鏈表這道題的另一種很的解法吧。介紹完常規操作鏈表的一些基本知識點后，現在回到快慢指針。 ??前幾天第一次在 Segmentfault 發文—JavaScript：十大排序的算法思路和代碼實現，發現大家似乎挺喜歡算法的，所以今天再分享一篇前兩個星期寫的 Leetcode 刷題總結，希望對大家能有所幫助。 ??本文首發于我的blog 前言 ??今天終于...
摘要：理解數組實現的滑動窗口，看下邊這個圖就可以了。第秒，開始計數，此時數組內開始存入計數周期，保存在數組第個位置，表示這是當前滑動窗口內的第個計數周期。在FireflySoft.RateLimit之前的版本中，進程內滑動窗口的實現是基于MemoryCache做的，雖然能夠正確的實現滑動窗口的算法邏輯，但是性能比較差，其吞吐量只有其它算法的1/4。性能為何如此之差呢？滑動窗口的原理我們先來看下滑動...
摘要：初始化隊列初始化一個存儲隊列中元素的數據結構，如果未傳入默認賦值空數組，傳入需先校驗類型是否正確。頭等艙和商務艙乘客的優先級要高于經濟艙乘客。在有些國家，老年人和孕婦或帶小孩的婦女登機時也享有高于其他乘客的優先級。 有一天，當回顧自己走過的路時，你會發現這些奮斗不息的歲月，才是最美好的人生。——弗洛伊德 隊列，英文 First In First Out 簡稱 FIFO，遵從先進先出的原...
摘要：如果不重復，判斷是否是類型，如果是紅黑樹，直接插入。條件為時執行鏈表轉紅黑樹，然后插入。為了避免尾部遍歷。添加元素時，如果超過閾值，就要進行擴容，如果兩個元素同時添加，線程和線程可能同時擴容。 1.HashMap結構 ????HashMap是存鍵值對(key-value)映射的數據結構，由數組+鏈表組成的，數組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的，如果定位到的數...
閱讀 1826·2023-04-26 02:51
閱讀 2857·2021-09-10 10:50
閱讀 3054·2021-09-01 10:48
閱讀 3612·2019-08-30 15:53
閱讀 1820·2019-08-29 18:40
閱讀 409·2019-08-29 16:16
閱讀 2031·2019-08-29 13:21
閱讀 1821·2019-08-29 11:07
