问题如下：
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
这个算法有很强的实用性，比如找到3组用户里面最相似的3元组，这里可以把abs替换为一个similarity函数即可。
下面的代码给出了一个最简单的Bruce force算法和一个优化算法。
package com.autofei.algorithm;
import java.util.Arrays;
public class GoogleMinimumDistance {
static void NavieMin(int[] a, int[] b, int[] c) {
int min = Integer.MAX_VALUE;
String triplet = "";
int[] tripletArray = new int[3];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b.length; j++) {
for (int k = 0; k < c.length; k++) {
tripletArray[0] = Math.abs(a[i] - b[j]);
tripletArray[1] = Math.abs(a[i] - c[k]);
tripletArray[2] = Math.abs(b[j] - c[k]);
Arrays.sort(tripletArray);
int distance = tripletArray[2];
if (distance < min) {
min = distance;
triplet = a[i] + "|" + b[j] + "|" + c[k];
}
}
}
}
System.out.println(triplet + " => " + min);
}
static void SmartMin(int[] a, int[] b, int[] c) {
int min = Integer.MAX_VALUE;
String tripletString = "";
int[] tripletArray = new int[3];
int i = 0;
int j = 0;
int k = 0;
while (i < a.length && j < b.length && k < c.length) {
tripletArray[0] = a[i];
tripletArray[1] = b[j];
tripletArray[2] = c[k];
Arrays.sort(tripletArray);
int tripletMax = tripletArray[2];
int tripletMin = tripletArray[0];
int distance = tripletMax - tripletMin;
if (distance < min) {
min = distance;
tripletString = a[i] + "|" + b[j] + "|" + c[k];
}
if (a[i] == tripletMin) {
i++;
} else if (b[j] == tripletMin) {
j++;
} else if (c[k] == tripletMin) {
k++;
}
}
System.out.println(tripletString + " => " + min);
}
public static void main(String[] args) {
int[] a = { 4, 10, 15, 28 };
int[] b = { 1, 3, 29 };
int[] c = { 5, 13, 28 };
GoogleMinimumDistance.NavieMin(a, b, c);
GoogleMinimumDistance.SmartMin(a, b, c);
}
}
转播
