457. 环形数组循环

RaoMeng 发布于2019-07-30 18:38 / 725人阅读

摘要：问题问题描述给定一组含有正整数和负整数的数组。假设数组首尾相接。判断数组中是否有环。你能写出时间复杂度为且空间复杂度为的算法吗示例给定数组有一个循环，从索引。给定数组没有循环。注意给定数组保证不包含元素。

问题 问题描述

给定一组含有正整数和负整数的数组。如果某个索引中的 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

云服务器私有云循环数组数组循环下标 linux 数组循环 json数组前端循环

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42786.html

Leetcode：刷完31道链表题的一点总结

摘要：既然说到地址空间了就顺带说一下上面环形链表这道题的另一种很的解法吧。介绍完常规操作链表的一些基本知识点后，现在回到快慢指针。前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。本文首发于我的blog 前言今天终于...

DevTalking 2019-08-23 17:50 评论0 收藏0
如何使用数组实现滑动窗口

摘要：理解数组实现的滑动窗口，看下边这个图就可以了。第秒，开始计数，此时数组内开始存入计数周期，保存在数组第个位置，表示这是当前滑动窗口内的第个计数周期。在FireflySoft.RateLimit之前的版本中，进程内滑动窗口的实现是基于MemoryCache做的，虽然能够正确的实现滑动窗口的算法逻辑，但是性能比较差，其吞吐量只有其它算法的1/4。性能为何如此之差呢？滑动窗口的原理我们先来看下滑动...

不知名网友 2021-11-29 10:50 评论0 收藏0
数据结构知否知否系列之 — 队列篇

摘要：初始化队列初始化一个存储队列中元素的数据结构，如果未传入默认赋值空数组，传入需先校验类型是否正确。头等舱和商务舱乘客的优先级要高于经济舱乘客。在有些国家，老年人和孕妇或带小孩的妇女登机时也享有高于其他乘客的优先级。有一天，当回顾自己走过的路时，你会发现这些奋斗不息的岁月，才是最美好的人生。——弗洛伊德队列，英文 First In First Out 简称 FIFO，遵从先进先出的原...

galois 2019-08-26 11:00 评论0 收藏0
Java集合_HashMap篇

摘要：如果不重复，判断是否是类型，如果是红黑树，直接插入。条件为时执行链表转红黑树，然后插入。为了避免尾部遍历。添加元素时，如果超过阈值，就要进行扩容，如果两个元素同时添加，线程和线程可能同时扩容。 1.HashMap结构 HashMap是存键值对(key-value)映射的数据结构，由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数...

MoAir 2019-08-16 18:39 评论0 收藏0