给一个datastream和一个fixed window size, 让我design一个class可以完成add number还有find average in the window. 就是不能用vector得用array.
当然用queue是最好的
package DataStreamAverage;
import java.util.*;
public class Solution {
int count;
int sum;
Queue<Integer> q;
public Solution() {
this.count = 0;
this.sum = 0;
this.q = new LinkedList<Integer>();
}
public ArrayList<Double> average (HashSet<Integer> set, int L) {
ArrayList<Double> result = new ArrayList<Double>();
Iterator<Integer> iter = set.iterator();
while (iter.hasNext()) {
int cur = iter.next();
q.offer(cur);
count++;
sum += cur;
if (q.size()>L) {
int front = q.peek();
sum -= front;
count--;
q.poll();
}
double aver = (double)sum/count;
result.add(aver);
}
return result;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
HashSet<Integer> set = new HashSet<Integer>();
for (int i=1; i<=10; i++) {
set.add(i);
}
Solution sol = new Solution();
ArrayList<Double> res = sol.average(set, 2);
System.out.println(res);
}
}
当然用fixed size array也可以，但是要小心，一个是要折回，二个是要删除数组元素之前存在的数
package DataStreamAverage;
import java.util.*;
public class Solution2 {
int count;
int sum;
int[] arr;
int pos;
public Solution2(int size) {
this.count = 0;
this.sum = 0;
this.arr = new int[size];
Arrays.fill(arr, Integer.MIN_VALUE);
this.pos = 0;
}
public ArrayList<Double> average (HashSet<Integer> set, int L) {
ArrayList<Double> result = new ArrayList<Double>();
Iterator<Integer> iter = set.iterator();
while (iter.hasNext()) {
int cur = iter.next();
if (pos == arr.length) {
pos = 0;
}
if (arr[pos] != Integer.MIN_VALUE) {
sum -= arr[pos];
count--;
}
arr[pos] = cur;
sum += arr[pos];
pos++;
count++;
double aver = (double)sum/count;
result.add(aver);
}
return result;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
HashSet<Integer> set = new HashSet<Integer>();
for (int i=1; i<=10; i++) {
set.add(i);
}
Solution2 sol = new Solution2(2);
ArrayList<Double> res = sol.average(set, 2);
System.out.println(res);
}
}