Friday, January 9, 2009

Find the index of first unique occurance of a character in a array - least time complexity

#include
//Complexity of the algorithm is 2n
int FindIndexOfFirstUniqueOccurance(char * arr)
{
if(arr == NULL)
return NULL;
//have a counter for each character
char iArr[256];
memset(iArr,0,256*sizeof(char));
char *ptr = arr;
while(*ptr)
{
iArr[*ptr]++;//increment the counter
ptr++;
}
ptr = arr;
while(*ptr)
{
if(iArr[*ptr] == 1)//the one that has a one set is the unique
return static_cast(ptr - arr);
ptr++;
}
return -1;
}
int _tmain(int argc, _TCHAR* argv[])
{
char * ptrarr = "abcbbcadfg";
int i = FindIndexOfFirstUniqueOccurance(ptrarr);
return 0;
}

No comments: