Ich hab mich mal an einer Aufgabe bei Leetcode versucht. Die Aufgabe lautet:

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Natürlich habe ich mich gleich an einer Aufgabe aus der Kategorie Hard versucht.

Hier gibt es natürlich mehrere Lösungsmöglichkeiten, die unterschiedlich komplex sind, aber auch unterschiedliche Laufzeitverhalten zeigen.

Kombination beider Arrays

Die einfachste Lösung ist natürlich, beide Arrays in einen neuen Array zu kopieren, diesen neuen Array sortieren zu lassen und dann den Median zu berechnen.

public static double findMedianSortedArraysSimple(int[] nums1, int[] nums2) {
	int[] combined = new int[nums1.length + nums2.length];
	if (nums1.length > 0)
		for (int i = 0; i < nums1.length; i++)
			combined[i] = nums1[i];
	if (nums2.length > 0)
		for (int i = 0; i < nums2.length; i++)
			combined[nums1.length + i] = nums2[i];
	Arrays.sort(combined);

	if (combined.length == 0) {
		return 0.0;
	} else if (combined.length % 2 == 0) {
		return 0.5 * (combined[combined.length / 2 - 1] + combined[combined.length / 2]);
	} else {
		return combined[combined.length / 2];
	}
}

Eine sehr einfache Lösung. Da aber der ganze Array sortiert wird, ist das die asymptotische Laufzeit proportional zu n*log(n) sein wird. Zudem benötigt man den doppelten Speicher, da man ja eine Kopie der Eingangswerte ablegen muss.

Lineare Suche

Eine bessere Variante ist es, mit zwei Indizes über beide Arrays zu iterieren, wobei jeweils der Index inkrementiert wird, dessen zugehöriger Wert geringer ist. Dies wird fortgeführt, bis die Hälfte der Einträge erreicht ist. Der Median lässt sich dann aus dem letzten Wert oder den letzten beiden Werten berechnen.

public static double findMedianSortedArraysLinear(int[] nums1, int[] nums2) {
	if (nums1.length == 0 && nums2.length == 0)
		return 0.0;

	int lengthOfBothArrays = nums1.length + nums2.length;
	int index1 = 0;
	int index2 = 0;
	int previous = 0;
	int current = 0;
	while (index1 + index2 <= lengthOfBothArrays / 2) {
		previous = current;
		
		if (index1 >= nums1.length) {
			current = nums2[index2];
			index2++;
			continue;
		}
		if (index2 >= nums2.length) {
			current = nums1[index1];
			index1++;
			continue;
		}
		if (nums1[index1] < nums2[index2]) {
			current = nums1[index1];
			index1++;
		} else {
			current = nums2[index2];
			index2++;
		}
	}
	if (lengthOfBothArrays % 2 == 0) {
		return 0.5 * (previous + current);
	} else {
		return current;
	}
}

Diese Vorgehensweise hat den Vorteil, dass keine Kopie der Eingangswerte angefertigt werden muss. Die asymptotische Laufzeit wird proportional zu n sein, also eine Verbesserung im Vergleich zum obigen Ansatz, aber noch nicht wie in der Aufgabe gefordert.

Binäre Suche

Meine beste Lösung ist eine Binäre Suche. Hier wird gesucht, wieviele der Elemente aus dem ersten Array unterhalb des Medians liegen. Die Anzahl der Elemente des zweiten Arrays, die unterhalb des Medians liegen, lässt sich damit berechnen. Das Kriterium ist, dass die jeweils größten berücksichtigten Werte beider Arrays jeweils kleiner sein müssen als die ersten nicht-berücksichtigten Werte des anderen Arrays.

public static int[] getCompositionOfLowerHalfBinary(int[] nums1, int[] nums2) {
	int requiredNumberForHalf = (nums1.length + nums2.length) / 2;

	int nEntriesToTakeMin = 0;
	int nEntriesToTakeMax = Math.min(nums1.length, requiredNumberForHalf);

	while (nEntriesToTakeMin < nEntriesToTakeMax) {
		int nEntriesToTakeFromFirst = (nEntriesToTakeMin + nEntriesToTakeMax) / 2;
		int nEntriesToTakeFromSecond = requiredNumberForHalf - nEntriesToTakeFromFirst;

		if (nEntriesToTakeFromSecond > nums2.length) {
			// increase number of entries taken from first array
			nEntriesToTakeMin = nEntriesToTakeFromFirst + 1;
			continue;
		}
		// check that this composition is correct. That means that the last chosen
		// elements are lower than
		// the first non-chosen one from the other array
		if (nEntriesToTakeFromFirst > 0 && nEntriesToTakeFromSecond < nums2.length) {
			if (nums1[nEntriesToTakeFromFirst - 1] > nums2[nEntriesToTakeFromSecond]) {
				nEntriesToTakeMax = nEntriesToTakeFromFirst - 1;
				continue;
			}
		}
		if (nEntriesToTakeFromSecond > 0 && nEntriesToTakeFromFirst < nums1.length) {
			if (nums2[nEntriesToTakeFromSecond - 1] > nums1[nEntriesToTakeFromFirst]) {
				nEntriesToTakeMin = nEntriesToTakeFromFirst + 1;
				continue;
			}
		}

		// already found the solution, no need to search further
		nEntriesToTakeMin = nEntriesToTakeFromFirst;
		break;
	}
	return new int[] { nEntriesToTakeMin, requiredNumberForHalf - nEntriesToTakeMin };
}

Mit dieser Information kann dann der Median berechnet werden. Er ergibt sich entweder als der kleinste nicht-berücksichtigte Wert oder als Mittelwert aus dem größten berücksichtigten Wert und dem kleinsten nicht-berücksichtigten Wert

public static double findMedianSortedArraysComp(int[] nums1, int[] nums2) {
	int[] composition = getCompositionOfLowerHalfBinary(nums1, nums2);
	int lengthOfBothArrays = nums1.length + nums2.length;

	if (lengthOfBothArrays == 0) {
		return 0.0;
	} else if (lengthOfBothArrays % 2 == 0) {
		// even number of elements -> return average of highest from the lower half and
		// the lowest from the higher half
		return 0.5 * (getHighestFromLowerHalf(nums1, nums2, composition)
				+ getLowestFromHigherHalf(nums1, nums2, composition));
	} else {
		// odd number -> return the lowest from the higher half
		return getLowestFromHigherHalf(nums1, nums2, composition);
	}
}

Die Berechnung dieser Werte ist relativ simpel:

private static int getHighestFromLowerHalf(int[] nums1, int[] nums2, int[] composition) {
	if (composition[0] == 0)
		return nums2[composition[1] - 1];
	if (composition[1] == 0)
		return nums1[composition[0] - 1];
	return Math.max(nums1[composition[0] - 1], nums2[composition[1] - 1]);
}

private static int getLowestFromHigherHalf(int[] nums1, int[] nums2, int[] composition) {
	if (composition[0] == nums1.length)
		return nums2[composition[1]];
	if (composition[1] == nums2.length)
		return nums1[composition[0]];
	return Math.min(nums1[composition[0]], nums2[composition[1]]);
}

Test

Ich habe die verschiedenen Ansätze gegeneinander getestet, um sicherzustellen, dass alle die gleichen Ergebnisse liefern. Die Testroutine sah wie folgt aus:

public static int[] getRandomSortedArray(int maxLength) {
	int[] nums = new int[(int) Math.floor(Math.random() * maxLength)];
	if (nums.length > 0) {
		nums[0] = (int) Math.floor(Math.random() * 10);
	}
	if (nums.length > 1) {
		for (int i = 1; i < nums.length; i++) {
			nums[i] = nums[i - 1] + (int) Math.floor(Math.random() * 10);
		}
	}
	return nums;
}

public static void test() {
	int[] nums1 = null;
	int[] nums2 = null;
	double medianSimple = 0.0;
	double medianLinear = 0.0;
	double medianComp = 0.0;
	do {
		nums1 = getRandomSortedArray(10);
		nums2 = getRandomSortedArray(10);

		System.out.print("nums1 (" + nums1.length + ") ");
		for (int i = 0; i < nums1.length; i++)
			System.out.print(" " + nums1[i]);
		System.out.println();
		System.out.print("nums2 (" + nums2.length + ") ");
		for (int i = 0; i < nums2.length; i++)
			System.out.print(" " + nums2[i]);
		System.out.println();

		medianSimple = findMedianSortedArraysSimple(nums1, nums2);
		medianLinear = findMedianSortedArraysLinear(nums1, nums2);
		medianComp = findMedianSortedArraysComp(nums1, nums2);
		System.out.println("medians: " + medianSimple + " " + medianLinear + " " + medianComp);
		System.out.println();
	} while (Math.abs(medianLinear - medianComp) < 0.1 && Math.abs(medianSimple - medianLinear) < 0.1);
}

Also eine Funktion, die zufällige, aber sortierte Arrays variabler Länge generiert, und eine Endlosschleife, die nach Fällen sucht, in denen die verschiedenen Funktionen unterschiedliche Ergebnisse zurückgeben.

Laufzeit

Und ich habe auch das Laufzeitverhalten gemessen, wenn auch auf sehr einfache Weise. Ich habe jeweils eine Million mal den Median eines Paares von Arrays berechnet. Die Länge der Arrays war dabei zufällig zwischen 0 und einem vorgegebenen Maximalwert.

public static void profile() {
	final int nTests = 1_000_000;
	final int[] nEntriesMax = new int[] { 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000 };

	int[][] nums = new int[nTests + 1][];

	long durations[] = new long[3];

	for (int nEntries = 0; nEntries < nEntriesMax.length; nEntries++) {
		for (int nTest = 0; nTest <= nTests; nTest++) {
			nums[nTest] = getRandomSortedArray(nEntriesMax[nEntries]);
		}

		long start = System.currentTimeMillis();
		for (int nTest = 0; nTest < nTests; nTest++) {
			findMedianSortedArraysSimple(nums[nTest], nums[nTest + 1]);
		}
		durations[0] = System.currentTimeMillis() - start;

		start = System.currentTimeMillis();
		for (int nTest = 0; nTest < nTests; nTest++) {
			findMedianSortedArraysLinear(nums[nTest], nums[nTest + 1]);
		}
		durations[1] = System.currentTimeMillis() - start;

		start = System.currentTimeMillis();
		for (int nTest = 0; nTest < nTests; nTest++) {
			findMedianSortedArraysComp(nums[nTest], nums[nTest + 1]);
		}
		durations[2] = System.currentTimeMillis() - start;

		System.out.println(nEntriesMax[nEntries] + "\t" + durations[0] + "\t" + durations[1] + "\t" + durations[2]);
	}
}

Die folgende Tabelle zeigt die benötigten Millisekunden für eine Million Aufrufe.

max. Länge Kombination Linear Binär
1 23 11 9
2 32 41 25
5 62 19 34
10 96 32 22
20 225 56 29
50 746 121 38
100 1598 232 55
200 2204 450 89
500 3224 1106 172
1000 5318 2167 209
2000 10314 4443 266
5000 24966 10946 394

Wie man sieht ist die binäre Suche am schnellsten und steigt auch am wenigsten für längere Arrays an. An der linearen Suche sieht man gut, wie die Laufzeit linear mit der maximalen Länge steigt. Es überrascht mich, dass die Laufzeit für die Kombination nicht stärker ansteigt, vielleicht hat Java hier schon Optimierungen für die Sortierung teilweise sortierter Arrays eingebaut.

Natürlich gibt es auch die komplette und kommentierte Java-Datei zum Download.