privateint size = 0; private ArrayList<Integer> source = new ArrayList<>();
publicvoidInsert(Integer num){ if (size == 0 || num < source.get(0)) { source.add(0, num); } elseif (num > source.get(size - 1)) { source.add(num); } else { Integer[] array = new Integer[source.size()]; source.toArray(array); int index = binaryIndex(array, num); source.add(index, num); } size++; }
public Double GetMedian(){ if (size % 2 != 0) { return Double.valueOf(source.get(size / 2)); } int a = source.get(size / 2); int b = source.get(size / 2 - 1); return (a + b) / 2.0; }
privateintbinaryIndex(Integer[] array, int key){ int index = 0; int left = 0; int right = array.length - 1; while (left <= right) { int mid = (right + left) / 2; if (array[mid] == key) { return mid; } if (array[mid] > key && array[mid - 1] < key) { index = mid; } if (array[mid] > key) { right = mid - 1; } else { left = mid + 1; } } return index; }
publicstaticvoidmain(String[] args){ int[] array = newint[]{2, 1, 4, 3, 6, 5, 8, 7, 10, 9}; Solution s = new Solution(); for (int i = 0; i < array.length; i ++) { s.Insert(array[i]); System.out.println(s.GetMedian()); } }