JAVA Solution using BitSet


  • 0
    L

    I think the operation "nextClearBit" may cause the time complexity over O(n), but I cant find another idea making the loop start at the number I havent visit before.

    public class Solution {
        public  boolean circularArrayLoop(int[] nums) {
            if(nums.length<2)
                return false;
            BitSet bitSet=new BitSet();
            int count=0,res,start=0;
            while(start<nums.length&&count<nums.length){
                res=step(bitSet,start,nums);
                if(res==0)
                    return true;
                else
                    start=res;
            }
            return false;
        }
        public  int step(BitSet bitSet,int pos,int[] nums){
            boolean direction=nums[pos]>0;
            int previous,start=pos;
            while(!bitSet.get(pos)&&direction==nums[pos]>0){
                bitSet.set(pos);
                previous=pos;
                pos=(pos+nums[pos]+nums.length)%nums.length;
                if(pos==previous){//ignore the 1 length circle
                    return bitSet.nextClearBit(0);
                }
            }
            if(bitSet.get(pos)&&start==pos) {//loop ended at where we start,so we get the circle
                return 0;
            }
            return bitSet.nextClearBit(0);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.