Compacting an array in C++

Hi,

Hope someone can give the simplest solution , and maybe it can be in O(n) if it is possible with explanations.

I need a function that takes sorted int array , and a size , and returns a new compact array after removing the duplicated elements , and the new size.


It can be solved in O(n^2) also .

Example:

1 , 3, 7, 7, 8, 9, 9, 9, 10

and it will return :
1 , 3 , 7 , 8, 9, 10 and size 5

Thank you

std::unique() will do this in-place in O(n).

and if we do not want to use STL , or std ready functions??

Well, that function can take pretty much anything----there's no need to get anything else STL-related involved except for the single function call. It can work with a bare array as easily as a std::vector. (Still, avoiding STL is stupid unless it's a teacher-imposed requirement.)

If you don't want to use the function, the algorithm it implements is pretty trivial. Essentially it loops through the array doing comparisons, and maintaining an index mapping as it goes; then it loops through the index array moving elements around, and returns the new length.

Using your example, the index array might be:

Code:

---

1, 3, 7, 7, 8, 9, 9, 9, 10
0, 1, 2,-1, 3, 4,-1,-1, 5

---

The return value would be size 6, not 5, incidentally. 5 is just the last used index.

You are right - Size is 6 not 5. My mistake
It is not a teacher requirement. It is an interview question. I have an interview , and I am trying to find the best solution for that.

hmm... actually, if the function is supposed to return a new compact array, perhaps the solution is to simply create a new array and copy over distinct elements with one pass over the source array.

But if the interview question did not forbid the use of the standard library, it would be a good idea to suggest the use of the standard library first.

What about if you are not allowed to create a new array. Just use the array that was given.

The two cases are not significantly different. It's simply a matter of whether you're moving elements to an earlier slot in the same array, or into a different array. The in-place case may be slightly more efficient since you don't need to copy the initial run of non-duplicated elements, but it's not enough of a difference to matter.

Note that in my above suggestion, the index array could be maintained implicitly rather than explicitly without much trouble.

Lindley already gave you a suggestion for an efficient solution along those lines in post #4.

Can you give me a code? I wil review and examine it to understand more

You will probably learn more by trying to implement an algorithm first.

For an interview question, I'd say the best possible answer would be to suggest std::unique(), since the question has laid out precisely what std::unique needs as a precondition. It's fairly obvious the question was written with std::unique() in mind.

Ok thank you :-)
I will check that deeply

Quote:

---

Originally Posted by wael.salman

What about if you are not allowed to create a new array. Just use the array that was given.

---

There's a very simple iterative solution.

You introduce two integer indexes, one for reading and one for writing. First you write code that just iterates through the whole array and copies each array number to itself using the two indexes. So the array is just copied onto itself in place.

Then you modify the above so that when the read index is incremented it's not just incremented by 1 as before. Instead it's incremented so it skips a sequence of equal numbers (but at the most to the end of the array of course).

When the read index has reached the end of the array, the write index holds the new array length.

what do you mean by:

First you write code that just iterates through the whole array and copies each array number to itself using the two indexes.????


Thank you