JAVA O(1) using Deque


  • 4
    P
    public class MovingAverage {
    
    	Deque<Integer> dq;
    	int size;
    	int sum;
    	public MovingAverage(int size) {
    		dq = new LinkedList<>();
    		this.size = size;
    		this.sum = 0;
    	}
    
    	public double next(int val) {
    		if (dq.size() < size) {
    			sum += val;
    			dq.addLast(val);
    			return (double) (sum / dq.size());
    		} else {
    			int temp = dq.pollFirst();
    			sum -= temp;
    			dq.addLast(val);
    			sum += val;
    			return (double) (sum / size);
    		}
    	}
    
    }

  • 0

    I think a simple Queue will do, not necessarily a Dequeue


  • 0
    P

    The advantage of using deque is you never need to think about the index. That's why I choose deque. And for this question, since it only need to operate the first index element and last index element, if you think deque is not necessary, I guess you are trying to solve this problem by using the simplest data structure. If so I think LinkedList is even better than your queue for this question.

    I can't see any big difference choosing queue or deque.


  • 0

    @publicstatic2 I didn't see the advantage here for deque. A linked list can do all the job. However, I think if you want to record the max in the window. Then deque would be a good choice.

    public class MovingAverage {
        private Queue<Integer> queue;
        private int size;
        private double average;
        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            queue = new LinkedList<Integer>();
            this.size = size;
            average = 0;
        }
        
        public double next(int val) {
            double sum = queue.size() * average;
            int remove = 0;
            if (queue.size() == size) {
                remove = queue.poll();
            }
            queue.offer(val);
            average = (sum - remove + val) / queue.size();
            return average;
        }
    }
    

  • 0
    P

    @Roderickgao Nice solution.


  • 0

    @pantherNation Thanks!


  • 0
    C

    this will failed
    More Details

    Input:
    ["MovingAverage","next","next","next","next"]
    [[3],[1],[10],[3],[5]]
    Output:
    [null,1.00000,5.00000,4.00000,6.00000]
    Expected:
    [null,1.00000,5.50000,4.66667,6.00000]


  • 0

    @publicstatic2 what is your point? what is the advantage of deque in this problem over queue? Using queue, you can also push from front and pop from back, do you need any other operation that deque can do but queue can not do?


  • 0
    P

    @Dragon.PW
    Of course you can use queue. But if it's a real queue, you can't push element from front. Luckily, in JAVA, Queue is realized by LinkedList. And in LinkedList it has two pointers, one points to head, the other points to tail. That's why you can push an element at the front.
    If you really want to use a simple data structure, I suggest you to use LinkedList.
    As a simple question like this, the interviewer only want to know what kind of data structure you should use if you need to add elements on both head and tail. If you answer Queue, you will have trouble.


  • 0

    @publicstatic2 but we don't need to push from front or pop from the back in this problem. this is why queue is enough


Log in to reply
 

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