Skip to content

Instantly share code, notes, and snippets.

@charlespunk
Last active December 13, 2015 17:19
Show Gist options
  • Save charlespunk/4947418 to your computer and use it in GitHub Desktop.
Save charlespunk/4947418 to your computer and use it in GitHub Desktop.
/*
Given three sorted interger arrays, A, B and C, find three indices (i,j,k) such that max(abs(A[i] - B[j]), abs(A[i]-C[k]), abs(B[j]-C[k])) is minimized.
Implement the function to return the minimal value.
Example:
A: [1,2,4,8,16,32]
B: [3,5,9,15,17,40]
C: [6,13,23,36,45]
The optimal solution is to choose (4,5,6) for a score of 2.
*/
int findMinimum(Integer[] A, Integer[] B, Integer[] C) {
}
public static int findMinimal(int[] inputA, int[] inputB, int[] inputC){
Node a = new Node(inputA);
Node b = new Node(inputB);
Node c = new Node(inputC);
PriorityQueue<Node> q = new PriorityQueue<>(3, new Comparator<Node>(){
public int compare(Node first, Node second){
return Integer.valueOf(first.getValue()).compareTo(Integer.valueOf(second.getValue());
}
});
q.add(a); q.add(b); q.add(c);
int min = Integer.MAX_VALUE;
Node temp;
while(true){
Node samll = q.poll();
Node median = q.poll();
Node large = q.poll();
int thisMin = large.getValue() - samll.getValue();
if(thisMin < min) min = thisMin;
if(small.pos < small.array.length - 1){
small.pos++;
q.offer(small); q.offer(median); q.offer(large);
}
else break;
}
return min;
}
class Node{
int[] array;
int pos;
Node(int[] input){
this.array = input;
this.pos = 0;
}
public getValue(){
return this.array[this.pos];
}
}
//if something wrong return -1, else return min
public static int findMinimal(int[] inputA, int[] inputB, int[] inputC){
int i, j, k = 0;
int min = Integer.MAX_VALUE;
if(inputA.length == 0 || inputB.length == 0 || inputC.length == 0) return -1;
while(i < inputA.length && j < inputB.length && k < inputC.length){
int thisMin = 0;
int thisMax = 0;
if(inputA[i] < inputB[j]){
if(inputA[i] < inputC[k]) thisMin = inputA[i++];
else thisMin = inputC[k++];
if(inputB[j] > inputC[k]) thisMax = inputB[j];
else thisMax = inputC[k];
}
else{
if(inputB[j] < inputC[k]) thisMin = inputB[j++];
else thisMin = inputC[k++];
if(inputA[i] > inputC[k]) thisMax = inputA[i];
else thisMax = inputC[k];
}
int thisDis = thisMax = thisMix;
if(thisDis < min) min = thisDis;
}
return min;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment