前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >457. Circular Array Loop

457. Circular Array Loop

作者头像
Dylan Liu
发布2019-07-01 14:02:14
4510
发布2019-07-01 14:02:14
举报
文章被收录于专栏:dylanliu

Description

Difficulty : Medium

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?

Solution

Points to be cared

  1. A loop starts and ends at a particular index with more than 1 element along the loop. It means a satisfied loop contains more than 1 element
  2. That the loop must be "forward" or "backward' means in a satisfied loop elements must be all postive or all negative

Mindpath: Since the give array is guaranteed to contain no 0, we start from a index which is not zero then loop through the array.

Calculate next index and do next steps

  1. check next index is zero or not, if it is, break
  2. set next index element to zero. It means that we visited that element
  3. check the direction, if changed, break
  4. check whether next index is equal the initial index, if so, we find a loop

Code blow:

代码语言:javascript
复制
func circularArrayLoop(nums []int) bool {
    size := len(nums)
    if size <= 1 {
        return false
    }

    for i:=0;i<size;i++{
        if nums[i] == 0{
            continue
        }
        direction := nums[i] > 0
        curIndex := i
        curVal := nums[i]
        counter := 1
        for true{
            curIndex = curIndex + curVal
            if curIndex >= size {
                curIndex = curIndex - size
            } else if curIndex < 0 {
                curIndex = curIndex + size
            }
            curVal = nums[curIndex]
            //traveled
            if nums[curIndex] == 0 {
                break
            }
            nums[curIndex] = 0
            //loop detected
            if curIndex == i &&  counter > 1{
                return true
            }
            // direction changed
            if !((direction && curVal >0) || (!direction && curVal < 0)){
                break
            }
            counter++
        }
    }
    
    return false
} 
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Solution
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档