s******e
发帖数: 108 | 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 | l*****a
发帖数: 14598 | 2 ArrayList for the first 3 requirements
for the 4th, create a new array as 2,10,10,10,80 and then u can get it
element
【在 s******e 的大作中提到】
: 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).
| g**e
发帖数: 6127 | 3 array list append不是每次都是O(1)吧
【在 l*****a 的大作中提到】
: ArrayList for the first 3 requirements
: for the 4th, create a new array as 2,10,10,10,80 and then u can get it
:
: element
| c*****n
发帖数: 96 | 4 then what's the time complexity for set(0, 100) operation using the example
given by LZ ?
【在 l*****a 的大作中提到】
: ArrayList for the first 3 requirements
: for the 4th, create a new array as 2,10,10,10,80 and then u can get it
:
: element
| l*****a
发帖数: 14598 | 5 http://docs.oracle.com/javase/6/docs/api/
The add operation runs in amortized constant time, that is, adding n
elements requires O(n) time.
【在 g**e 的大作中提到】
: array list append不是每次都是O(1)吧
| l*****a
发帖数: 559 | | w*******y
发帖数: 85 | 7
nice.
【在 l*****a 的大作中提到】
: ArrayList for the first 3 requirements
: for the 4th, create a new array as 2,10,10,10,80 and then u can get it
:
: element
| f*****e
发帖数: 2992 | 8 add a fake value to every element:
fake(a[i+1])=max{fake(a[i]), a[i+1]}
binary search val among fake(a[1...n])
element
【在 s******e 的大作中提到】
: 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).
| z****x
发帖数: 25 | 9 what about set() operation?
【在 f*****e 的大作中提到】
: add a fake value to every element:
: fake(a[i+1])=max{fake(a[i]), a[i+1]}
: binary search val among fake(a[1...n])
:
: element
|
|
