stevedunstan.com
BAN USERThis was pretty challenging. But fun! Here is my solution:
public class Interleave {
// O(n log n)
public void interleave(Object[] a) {
if (a == null || a.length <= 2) return;
if (a.length % 2 == 1) throw new IllegalArgumentException("Must be an even number of pairs");
split(a, 0, a.length-1);
}
private void split(Object[] a, int left, int right) {
int size = right-left+1;
if (size <= 2) return;
int mid = left + (size/2);
// Pretty ugly in terms of time complexity, adds O(size/2).
// As an optimization, instead of checking for multiples of 4,
// check for powers of 2, and slide over that way.
// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// x x x x a3 a4 a5 a6 a7 a8 a9 b3 b4 b5 b6 b7 b8 b9
// size is 14
// swap indicies 10 and 16
// move right index from 17 to 15
if ((size % 4) != 0) {
// e.g., size is 14, swap 10th with 16th
shift(a, mid-1, mid, size/2-1);
right = right - 2;
size = size - 2;
mid = mid - 1;
}
// slide over the third quarter to the second quarter
shift(a, left + (mid - left) / 2, mid, size/4);
// O(log n)
split(a, left, mid-1);
split(a, mid, right);
}
// O(count)
private void shift(Object[] a, final int to, final int from, final int count) {
int i = to;
int j = from;
int counter = 0;
while (counter < count) {
swap(a, i++, j++);
counter++;
}
}
// O(1)
private void swap(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
- stevedunstan.com February 25, 2018