G面経prepare:Data Stream Average
6367 ワード
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でもいいですが、1つは折り返し、2つは配列要素を削除する前に存在する数です.
1 package DataStreamAverage;
2
3 import java.util.*;
4
5 public class Solution2 {
6 int count;
7 int sum;
8 int[] arr;
9 int pos;
10
11 public Solution2(int size) {
12 this.count = 0;
13 this.sum = 0;
14 this.arr = new int[size];
15 Arrays.fill(arr, Integer.MIN_VALUE);
16 this.pos = 0;
17 }
18
19
20 public ArrayList<Double> average (HashSet<Integer> set, int L) {
21 ArrayList<Double> result = new ArrayList<Double>();
22 Iterator<Integer> iter = set.iterator();
23 while (iter.hasNext()) {
24 int cur = iter.next();
25 if (pos == arr.length) {
26 pos = 0;
27 }
28 if (arr[pos] != Integer.MIN_VALUE) {
29 sum -= arr[pos];
30 count--;
31 }
32 arr[pos] = cur;
33 sum += arr[pos];
34 pos++;
35 count++;
36 double aver = (double)sum/count;
37 result.add(aver);
38 }
39 return result;
40 }
41
42
43 /**
44 * @param args
45 */
46 public static void main(String[] args) {
47 // TODO Auto-generated method stub
48 HashSet<Integer> set = new HashSet<Integer>();
49 for (int i=1; i<=10; i++) {
50 set.add(i);
51 }
52 Solution2 sol = new Solution2(2);
53 ArrayList<Double> res = sol.average(set, 2);
54 System.out.println(res);
55 }
56
57 }