Rams
BAN USERHere is my version.
Output:
-bash-4.1$ gcc array_replace.c ; ./a.out
BEFORE - 0, 0, 3, 1, 2, 0, 0, 3, 1, 0, 0, 4, 3, 5, 6,
AFTER - 0, 0, 1, 2, 0, 0, 1, 0, 0, 4, 3, 5, 6,
Below is the code. The complexity seems to be O(n) - we don't parse the array thrice but only once. We go back to previous indices only to replace 003 with 00
(the problem is not as simple as it might seem in the first glance - no forward lookup, need to shift the elements in case any hits (match with 0, 0, 3), since the replacement is less than 3 elements (two elements) - idash variable is used for the purpose.
#include <stdio.h>
#define DATA_SIZE 15
#define FIND_SIZE 3
#define REPL_SIZE 2
print_array(char *string, int array[], int array_size)
{
int i = 0;
printf("%s - ",string);
for (i = 0; i < array_size; i++)
{
printf("%d, ",array[i]);
}
printf("\n");
}
int overwrite(int a[], int index, int repl[], int repl_size)
{
int i = 0;
for (i = 0; i < repl_size; i++)
{
a[index + i] = repl [i];
}
}
int replace_array(int a[], int size, int find[], int find_size, int repl[], int repl_size)
{
int i = 0, j = 0, k = 0;
int findi = 0;
int broken = 1;
int repl_count = 0;
int idash = 0;
for (i = 0; i < size; i ++, idash ++)
{
if (broken)
{
findi = 0;
broken = 0;
}
// if (repl_count > 0)
{
a[idash] = a [i];
}
if(a[i] == find[findi])
{
findi ++;
if (findi == find_size)
{
overwrite(a, idash - (find_size - 1) , repl, repl_size);
repl_count ++;
//printf("overwriting string find_size:%d, repl_size:%d, \n", find_size, repl_size);
idash -= (find_size - repl_size);
broken = 1;
}
}
else
{
broken = 1;
}
}
return repl_count;
}
int main(void)
{
int data[DATA_SIZE] = { 0, 0, 3, 1, 2, 0, 0, 3, 1, 0, 0, 4, 3, 5, 6};
int find[FIND_SIZE] = { 0, 0, 3};
int replace[REPL_SIZE] = { 0, 0};
int repl_count = 0;
print_array("BEFORE", data, DATA_SIZE);
repl_count = replace_array(data, DATA_SIZE, find, FIND_SIZE, replace, REPL_SIZE);
print_array("AFTER ", data, DATA_SIZE- repl_count * (FIND_SIZE - REPL_SIZE));
}
Time Complexity = O(n2)
- Rams January 28, 2014Space complexity = O(n)
I have not checked for accuracy, but this method is not practically useful, since you have allocated the the array on stack. Try to use new operator for arrays.