Sign in to follow this  

Deleting element from an array

This topic is 3373 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

This topic is 3373 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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