RearrangeInputToTarget { public static void rearrange(int[] input, int[] target) { assert (input.length == target.length); Map<Integer, Integer> map = new HashMap<Integer, Integer>(); buildIndex(input, map); int zeroIndex = com.github.kowshik.bigo.common.ArrayUtils.findIndex(input, 0); int numMoves = 0; while (numMoves < input.length) { if (target[zeroIndex] == 0) { int outOfOrderIndex = findFirstOutOfOrderIndex(input, target); if (outOfOrderIndex == -1) { return; } map.put(input[outOfOrderIndex], zeroIndex); com.github.kowshik.bigo.common.ArrayUtils.swap(input, zeroIndex, outOfOrderIndex); zeroIndex = outOfOrderIndex; } else { int nextZeroIndex = map.get(target[zeroIndex]); com.github.kowshik.bigo.common.ArrayUtils.swap(input, zeroIndex, nextZeroIndex); zeroIndex = nextZeroIndex; numMoves++; } } }  static void rearrange(int[] input, int[] target);  }
@Test public void rearrange_inputIsSameAsOutput() { int[] target = { 5, 0, 3, 2, 9 }; int[] input = { 5, 0, 3, 2, 9 }; RearrangeInputToTarget.rearrange(input, target); assertArrayEquals(input, target); }
@Test public void rearrange_inputIsDifferentFromOutput() { int[] target = { 5, 0, 3, 2, 9 }; int[] input = { 0, 2, 5, 9, 3 }; RearrangeInputToTarget.rearrange(input, target); assertArrayEquals(input, target); }
@Test public void rearrange_inputIsDifferentFromOutputAndZeroGetsLocked() { int[] target = { 0, 5, 3, 2, 9 }; int[] input = { 0, 2, 5, 9, 3 }; RearrangeInputToTarget.rearrange(input, target); assertArrayEquals(input, target); }