Sign in to follow this  
smc

Deleting element from an array

Recommended Posts

This is a HW problem, so please do not post a solution. I simply want to know if the second part of this problem is solvable. As it stands now I do not think so. Problem: Given an array [1 ... n] devise an algorithm to accomplish the following tasks such that the algorithms time does not depend on the array size n. a) Delete the i'th element of an unsorted array 1 <= i <= n. Trivial: Swap the i'th element with the n'th element. b) Delete the i'th element of a sorted array ... Not so trivial... Edit: Solution... there is no clean solution as with the unsorted array. The only way to do this without shifting is to mark the array with a value outside the range of values for which the array elements hold. I originally though of this, but figured it was outside of the problem statement as it adds state to the array elements. I guess over thinking can get you no where sometimes. [Edited by - smc on September 19, 2008 3:21:44 PM]

Share this post


Link to post
Share on other sites
Quote:
Trivial: Swap the i'th element with the n'th element.

That's not a simple removal.
That actually changes the order if the elements. If order doesn't matter, then it's not an array, it's a set.

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
That actually changes the order if the elements. If order doesn't matter, then it's not an array, it's a set.


What?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this