Get first Greater in a array# JobHunting - 待字闺中
s*e
1 楼
Implement an array on ints which supports
1) void lookup(int idx) : value stored at idx, in amortized O(1) time.
2) void append(int value) : adds a value at the end of the array, in
amortized
O(1) time.
3) void set(int idx, int val) : sets the value at idx to val. if idx >
length
, throws an error. Complexity amortized O(1) time.
4) int GetFirstMaxIndex(int val): Gets the first index such that the element
at the idx is > val. Complexity O(logn).
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80
1) void lookup(int idx) : value stored at idx, in amortized O(1) time.
2) void append(int value) : adds a value at the end of the array, in
amortized
O(1) time.
3) void set(int idx, int val) : sets the value at idx to val. if idx >
length
, throws an error. Complexity amortized O(1) time.
4) int GetFirstMaxIndex(int val): Gets the first index such that the element
at the idx is > val. Complexity O(logn).
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80