假设我们有一个整数数组int[] A = {1,2,3,4,5,6,7,8,9}。
假设我们想要从A中选取一些随机整数,并将其随机重新插入数组中的其他位置,如下所示:
首先拿一些int number = A[random.nextInt(A.length)]
假设我们随机选择5,然后将其随机重新插入到7和8之间,这样A就变成了{1,2,3,4,6,7,5,8,9}。
现在,我们显然可以通过创建一些临时变量int temp = 5,将子数组{6,7}向左移位,然后将5重新插入到之前由7占用的索引中,来执行重新插入操作。但是,有没有一种更有效的方法来做到这一点,而不需要移动一些子数组(并且不需要更改到另一个数据结构,如链表)?因为很明显,我们有一些O(n)的最坏情况,我们随机选择A[0],然后必须将它插入到A[A.length]中,要求数组中的所有元素都进行移位,而我不希望这样做。
发布于 2019-05-08 07:18:36
我没有对此做过很多测试,但这里有一个解决方案的快速草图。
/**
* Shifts the element of the given {@code array} presently at index {@code fromIndex} to
* {@code toIndex}.
*
* @param array the array whose elements should be shifted
* @param fromIndex the current index of the element to shift
* @param toIndex the destination index of the element to shift
*/
public static void shift(final Object array,
final int fromIndex,
final int toIndex) {
if (fromIndex == toIndex) {
return;
}
final Object atIndex = Array.get(array, fromIndex);
if (toIndex > fromIndex) {
System.arraycopy(array, fromIndex + 1, array, fromIndex, toIndex - fromIndex);
} else {
System.arraycopy(array, toIndex, array, toIndex + 1, fromIndex - toIndex);
}
Array.set(array, toIndex, atIndex);
}虽然一般的方法与您所描述的差不多,但我怀疑System.arraycopy的性能(几乎)比您在这方面获得的任何其他东西都要好。不过,我可能大错特错了。
https://stackoverflow.com/questions/56031452
复制相似问题