Jump to content
  • Advertisement
Sign in to follow this  
smc

Deleting element from an array

This topic is 3591 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!