Quote:Original post by MOVSW
My coworker is sort of an asshat, i bet this algorithm is probably not even optimizable to O(n).
How can you bet that if someone has ALREADY explained how to do it in O(n) in this very thread?
Optimizing this algorithm
How can you bet that if someone has ALREADY explained how to do it in O(n) in this very thread?
As a side-note: you can early-out when the values of the 2 remaining arrays are larger than the value of first array to reach the end.
If you're implimenting it as I stated, go with the second, cleaner one. The first implimentation is actually pretty cracked-out in comparison. It was just the first way that came to mind. I'd drop it like a bad habit in favor of the second.
If you're implimenting it as I stated, go with the second, cleaner one. The first implimentation is actually pretty cracked-out in comparison. It was just the first way that came to mind. I'd drop it like a bad habit in favor of the second.
Actually, using a binary search on the two inner loops would increase the speed quite a bit. It would be O(a*logb*logc), which is a lot better than O(a*b*c). (You should also make sure the outer loop works with the smallest array.) However, your co-worker is right, there is an even better way to do it.
I believe that should do the same thing, and it's O(a+b+c). The algorithm takes advantage of the fact that all three arrays are sorted, and it keeps bumping the index that has the smallest value up until all three match or the end of an array is hit. It would also be easy to modify this algorithm to return a list of matches. Instead of breaking out of the loop, just add the three indices to the end of a list.
EDIT: This is the same solution Ravyne posted, but you didn't seem to notice that he had provided the solution.
EDIT: Either that, or I didn't notice what you meant by "I guess I took to long to write that post." ;-)
bool bDone = false;int ai=0, bi=0, ci=0;while(!bDone){ if(a[ai] == b[bi] && b[bi] == c[ci]) break; else { if(a[ai] <= b[bi] && a[ai] <= c[ci]) ai++; else if(b[bi] <= a[ai] && b[bi] <= c[ci]) bi++; else if(c[ci] <= a[ai] && c[ci] <= b[bi]) ci++; if(ai, bi, or ci went out of bounds) bDone = true; }}if(!bDone) cout << "Match found";I believe that should do the same thing, and it's O(a+b+c). The algorithm takes advantage of the fact that all three arrays are sorted, and it keeps bumping the index that has the smallest value up until all three match or the end of an array is hit. It would also be easy to modify this algorithm to return a list of matches. Instead of breaking out of the loop, just add the three indices to the end of a list.
EDIT: This is the same solution Ravyne posted, but you didn't seem to notice that he had provided the solution.
EDIT: Either that, or I didn't notice what you meant by "I guess I took to long to write that post." ;-)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
