Printable View
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:
The return value would be size 6, not 5, incidentally. 5 is just the last used index.Code:1, 3, 7, 7, 8, 9, 9, 9, 10
0, 1, 2,-1, 3, 4,-1,-1, 5
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
There's a very simple iterative solution.Quote:
Originally Posted by wael.salman
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
Like this,Quote:
Originally Posted by wael.salman
The array and array_size are defined elsewhere.Code:int w=0; // write index
int r=0; // read index
while (r < array_size) {
array[w++] = array[r]; // copy number, increment write index by 1
r++; // increment read index by 1
}
The above just copies the array on itself. You modify it so the r index is incremented in each iteration to skip a whole sequence of equal numbers. The w index is incremented as before. The effect is that only one number of any equal number sequence is copied.
doublepost by mistake
The above just copies the array on itself... Why we should do that??
Can you give me full solution so I can understand.
You often develop a solution in this way, incrementally in steps. You start with something simple and modify it to do something more complex.Quote:
Originally Posted by wael.salman
If you don't understand why the modification I've suggested leads to a solution to your problem then there's no way you'll ever understand a complete solution if I posted one.
The only way for you to get something out of this is to start fiddling around with the code I posted and not stop until you arrive at a solution.
http://www.cplusplus.com/reference/algorithm/unique/Quote:
Originally Posted by wael.salman
If you don't want to use std::unique, then just use the algorithm.
bool bRemoveDuplicates(int array[], int iSize){
if(iSize <1)
return false;
if(array == NULL)
return false;
if(iSize == 1)
return true;
int left_comp = 0;
int right_comp = 1;
bool start_move = false;
int hole = iSize;
for(; right_comp <iSize;right_comp++,left_comp++){
if(array[left_comp] == array[right_comp]){
if(!start_move){
start_move = true;
hole = right_comp;
}
}
else if(start_move){
array[hole++] = array[right_comp];
}
}
for(;hole<iSize;hole++){
array[hole] = 0;
}
return true;
}