zFaust
BAN USERThis solution is of O(k*log k) complexity
I will call the least side of a sorted list the left side and the greatest side the right side
1. take only the min and max of every list and discard all other elements, now we have k lists each of size at most 2.
2. Merge these lists to form list L and meanwhile create an array A of equal size(indeed this can be a bit field, for we only need two values for each entry); during the forming of list L, for every element of L, record in corresponding index of A whether this element was the min or max of the original k lists.
3. Starting from the left side of L, proceed right one by one until an element that is the right side of one of the original k list is reached, this can be verified by indexing A. This element will mark the left side of the desired range.
4. Repeat step 3. from the right side of L. And obtain the right side of the desired range.
Comlexity:
step 1 is of O(1), step 3. and 4. combined will not take more than 2*k looping. Step 2. is the merging of less than 2*k elements and thus O(k*log(k))
Apparently |a-b|+|b-c|+|c-a| is the same as 2*(max(a,b,c)-min(a,b,c)), so we are just gonna try to minimize max(a,b,c)-min(a,b,c)
First we need to iterate each of the array to find their respective max and min so to determine their range;
I split all the possibilities into two cases:
1. At least two of the arrays are disjoint, this can be determined from comparing their max and min. In this case, we only pick an array A and find the other array B, so that B is the furthest disjoint array of A, for example if A is disjoint with both B and C, such that A. max<B.min and A.max<C.min, additionally we know B.min < C.min, then we pick C; now apparently the desired combination will require C.min and A.max, which will determine the desired minimum, and we only need to pick any element b from B such that b<=C.min and b>=B.min;
2. None of the two arrays out of the three are disjoint of each other. Meaning they all have joint sections. For this case we first need to find the common joint range of all three(guaranteed to exist since none of them disjoint of each other), since the desired combination must be around this range, which will be between max(A.min, B.min, C.min) and min(A.max, B.max, C.max), I will call this range r, bounded by r.min and r.max. Second, we iterate through all three list again and discard all elements outside this range except for the element immediately next to the range, specifically for an element a of array A, we keep a
where A[A.min - r.min] is the sub-array of A bounded by A.min and r.min. Third, now it's the algorithm proper, heap sort and merge all three lists in to list L1, keep an equal size array L2 to record from which of the three array A,B or C every element in L1 came from. Finally, iterate through L1 from the left, and for every element e encountered, calculate the difference between the max and min elements in the sub-array bounded left by e and such that contains at least one element from each of the 3 original lists. If the difference is the least of all differences found, record the difference and the sub-array.
- zFaust September 28, 2015After the iteration, we will have the min, and the three numbers will be the resulting sub-array's starting and ending element plus any element between them that's from the third array