首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何高效地在数组中随机重新插入元素

问如何高效地在数组中随机重新插入元素
EN

Stack Overflow用户
提问于 2019-05-08 06:56:04
回答 1查看 56关注 0票数 0

假设我们有一个整数数组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]中,要求数组中的所有元素都进行移位,而我不希望这样做。

EN

回答 1

Stack Overflow用户

发布于 2019-05-08 07:18:36

我没有对此做过很多测试,但这里有一个解决方案的快速草图。

代码语言:javascript
复制
/**
 * 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的性能(几乎)比您在这方面获得的任何其他东西都要好。不过,我可能大错特错了。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/56031452

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档