[算法] 找到最相邻的3元组

问题如下：

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);
	}
}