You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

* Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))

* Please give a solution in O(n) time complexity

Answer;

Note it contains the paired as well as the tuple type solution. I didnt know how to do so i trial it with a pair type..

EDIT: Also on the web I noticed several other solutions that just move the min number I didnt click until now.. But be careful the mins movement is a property of this particular distance function if that changes then moving the min might not be the best course of action.

#include <math.h> #include <iostream> #include <list> using namespace std; #define MAX3(a,b,c) ((a > b) ? ((a > c) ? a : c) : ((b > c) ? b : c)) #define DIST2(a,b) abs(a-b) #define DIST3(a,b,c) MAX3(abs(a-b),abs(a-c),abs(b-c)); struct Tuple { int a; int b; int c; Tuple(int _a, int _b, int _c) { a = _a; b = _b; c = _c; } }; typedef listListTuple; void min_tuple(int* a, int* b, int* c, int sizea, int sizeb, int sizec) { ListTuple best_tuple; //best_pairs.push_back(Pair(0,0)); int best = DIST3(a[0], b[0], c[0]); int i, j, k; i = j = k = 0; while( (i < sizea) && (j < sizeb) && (k < sizec) ) { //check the current for best status int dist = DIST3(a[i], b[j], c[k]); if(dist < best) { best_tuple.clear(); best_tuple.push_back(Tuple(i,j,k)); best = dist; } else if(dist == best) best_tuple.push_back(Tuple(i,j,k)); //move to the next possible minium... int dist_i = DIST3(a[i+1], b[j], c[k]); int dist_j = DIST3(a[i], b[j+1], c[k]); int dist_k = DIST3(a[i], b[j], c[k+1]); if(dist_i < dist_j) if(dist_i < dist_k) i++; else k++; else if(dist_j < dist_k) j++; else k++; cout << i << "," << j << "," << k << " -> "; } cout << endl; cout << "best tuples are: " << endl; for(ListTuple::iterator pit = best_tuple.begin(); pit != best_tuple.end(); pit++) { Tuple& t = *pit; cout << "index: " << t.a << "," << t.b << "," << t.c << " values: "<< a[t.a] << "," << b[t.b] << "," << c[t.c] << endl; } cout << endl; cout << "best distance was: " << best; } struct Pair { int a; int b; Pair(int _a, int _b) { a = _a; b = _b; } }; typedef list ListPair; void min_pair(int* a, int* b, int sizea, int sizeb) { ListPair best_pairs; //best_pairs.push_back(Pair(0,0)); int best = DIST2(a[0], b[0]); int i, j; i = j = 0; while( (i < sizea) && (j < sizeb) ) { //check the current for best status int dist = DIST2(a[i], b[j]); if(dist < best) { best_pairs.clear(); best_pairs.push_back(Pair(i,j)); best = dist; } else if(dist == best) best_pairs.push_back(Pair(i,j)); //move to the next possible minium... if(i < sizea) if(j < sizeb) if(DIST2(a[i+1], b[j]) < DIST2(a[i], b[j+1])) i++; else j++; else i++; else j++; cout << i << "," << j << " -> "; } cout << endl; cout << "best pairs are: "; for(ListPair::iterator pit = best_pairs.begin(); pit != best_pairs.end(); pit++) { Pair& p = *pit; cout << "index: " << p.a << "," << p.b << " values: "<< a[p.a] << "," << b[p.b] << endl; } cout << endl; cout << "best distance was: " << best; } void print(int* data, int size) { for(int i = 0; i < size; i++) cout << data[i] << " "; cout << endl; } void bubblesort(int data[], int size) { bool change = true; int tmp; while(change) { change = false; for(int i = 0;i < size-1;i++) if(data[i] > data[i+1]) { tmp = data[i]; data[i] = data[i+1]; data[i+1] = tmp; change = true; } } } #define COUNT 10 int main() { int data1[COUNT]; int data2[COUNT]; int data3[COUNT]; srand(time(NULL)); for(int i = 0; i < COUNT; i++) { data1[i] = rand()%200; data2[i] = rand()%200; data3[i] = rand()%200; //data1[i] = -20 + i*3; //data2[i] = i*5; } bubblesort(data1, COUNT); bubblesort(data2, COUNT); bubblesort(data3, COUNT); print(data1, COUNT); print(data2, COUNT); print(data3, COUNT); min_pair(data1, data2, COUNT, COUNT); cout << endl; min_tuple(data1, data2, data3, COUNT, COUNT, COUNT); }

## No comments:

## Post a Comment