Quote:
Originally Posted by cheerios
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.)
|
If you could solve both problems independently:
a) just set array[i ] to zero/null.
b) use linked lists (pointers). simply drop item i, have item [i-1] point to item [i+1].
To solve both problems at once seems impossible. With a normal array, problem b seems impossible, because sorting an array takes n steps at least. With linked lists, problem a seems impossible, because deleting item i is dependent on the size of n (you have to search for the item).
I got the big olde book of data structures, which tells me that no matter which data structure you use, either a or b depends on the array size n in some way. The most efficient option I saw was a heap (
https://users.cs.jmu.edu/bernstdh/we...troduction.php).