Siddharth said:
Heres one I heard-
For an array of integers in sorted order, which can have multiple
occurences of any integer, form an array which lists the integers just
once first, and then their duplicates in sorted order.
Thus for
1 1 1 2 2 3 9 9 9 10
the o/p should be
1 2 3 9 10 1 1 2 9 9
The algorithm should be O(n) in running time...and should use only
O(1) extra space.
Siddharth Taneja
This one seems to be more appropriate to comp.programming
rather than c.l.c . So, setting the right follow-up hence.
But anyway, here is the code ...
/*****************************
$Id$
Created By: Karthik Kumar
*****************************/
#include <stdlib.h>
#include <stdio.h>
void reorder_array(int * in, size_t num, int * out);
void print_array(int * a, size_t num);
int main() {
int out[10];
int in[] = { 1 ,1 ,1 ,2 ,2, 3, 9, 9, 9 , 10 };
reorder_array(in, 10, out);
print_array(out, 10);
return EXIT_SUCCESS;
}
void reorder_array(int * in, size_t num, int * out) {
size_t i;
size_t repetitions;
int lastvisited;
size_t nextneedle;
size_t dupneedle;
repetitions = 0;
lastvisited = in[0];
for (i = 1 ; i < num ; i++) {
if ( in
== lastvisited ) {
repetitions++;
}
lastvisited = in;
}
/** Count the number of repetitions in the input array */
lastvisited = in[0];
nextneedle = 1; /* Normal Index */
dupneedle = num - repetitions;
/* Index where duplicate entries start */
out[0] = in[0]; /* Copy the first element anyway */
for (i = 1 ; i < num ; i++) {
if ( in != lastvisited ) {
out[nextneedle++] = in;
} else {
out[dupneedle++] = in;
}
lastvisited = in;
}
printf("\n Repetitions: %d\n", repetitions );
}
void print_array(int * a, size_t num) {
size_t i ;
for (i = 0 ; i < num ; i++) {
printf("%d ", a);
}
printf("\n");
}
