Ok, I'm working on my algorithms homework, and I come across this problem:
Quote:
Describe how one can implement each of the following operations on an array so that the time it takes does not depend on the array's size n.
a. Delete the ith element of an array(1<=i<=n).
b. Delete the ith element of a sorted array (the remaining array has to stay sorted, of course.)
|
now, I'm honestly baffled and the chapter has nothing to say about array element deletion. Because in Data Structures they tought us that array's downside was that they were slow to delete and insert into the middle of the array, because a new array had to be created, and every value had to be copied in, with the correct value added or left out. now, this question implies that is not true, and I have no clue how that could be. Any hints?