HVT
BAN USER- (void)trimmingSpaces
{
char string[] = " Hello World, this is a big space and I'm adding few more spaces to this";
int wordCount = 0;
int charCount = 0;
int spaceCount = 0;
bool shouldIncrementWordCount = false;
int i =0;
for (i =0; string[i]!='\0'; i++)
{
if (string[i] == ' ') {
if (shouldIncrementWordCount) {
wordCount++;
}
spaceCount++;
shouldIncrementWordCount = false;
}
else
{
if (spaceCount==0 || spaceCount==wordCount) {
charCount++;
shouldIncrementWordCount = true;
continue;
}
if (wordCount>0) {
if (!shouldIncrementWordCount) {
string[i-spaceCount+wordCount+1] = ' ';
}
string[(i-spaceCount)+wordCount] = string[i];
}
else
{
string[i-spaceCount] = string[i];
}
string[i] = ' ';
charCount++;
shouldIncrementWordCount = true;
}
}
string[charCount+wordCount] = '\0';
}
This is a generic program with 0 based index. For this problem the kidx would be 0.
I use a binary search to complete the program.
int indexKthElementInASortedArray(int kIdx, int elementInArray, int sortedArr[], int count)
{
int idx = indexOfElementInArray(elementInArray, 0, count-1, sortedArr);
while (sortedArr[idx] == elementInArray) {
idx--;
}
if (sortedArr[idx+kIdx+1]==elementInArray) {
return idx+kIdx+1;
}
else
return -1;
return -1;
}
int indexOfElementInArray(int elementInArray, int lo, int hi, int input[])
{
int midIdx = (lo+hi)/2;
if (hi<lo) {
return -1;
}
if (midIdx<=0)
return midIdx;
int midElement = input[midIdx];
if (elementInArray>midElement) {
return indexOfElementInArray(elementInArray, midIdx+1, hi, input);
} else if (elementInArray<midElement) {
return indexOfElementInArray(elementInArray, lo, midIdx-1, input);
} else {
return midIdx;
}
}
LSD Radix Sort would be the best
- HVT June 10, 2014