java - 上移、下移、指定位置

Question

我知道这看起来应该很简单，但由于某种原因，我无法理解解决这个问题的算法，所以我将就这个问题与社区联系。

我有一个如下所示的类:

class MapElementModel {
    int id;
    String name;
    int position;
    //other fields ommitted for space reasons

    //getters and setters
}

现在我将 MapElementModel 存储在标准 ArrayList 中。用户想要在列表中向上、向下移动元素，或者为 MapElementModel 指定新位置。该列表根据 MapElementModel.position 排序。

所以基本上，如果用户将项目 14 移动到位置 3，则该项目需要插入位置 3，位置字段需要更改为 3，并且所有后续位置都需要相应更改。

同样，用户可以点击“上移”按钮并将位置 9 处的项目移动到位置 8。同样，所有剩余的 MapElementModel.position 项目都需要相应地更改其位置字段。

最后，用户可以点击“下移”按钮并将列表中的项目向下移动。同样，所有 MapElementModel.position 字段都必须更新。

谁有好的办法解决这个问题吗？感谢您的帮助!

Answer 1

您说，“列表是根据 MapElementModel.position 排序的”，所以我的答案将基于此。如果根据 MapElementModel.id 排序，这将是不同的算法。

将ArrayList视为您有序的项目集合。无需将位置“存储”在 MapElementModel 中，只需让 ArrayList 中元素的索引作为其位置即可。例如，如果您的 ArrayList 具有元素 ["Red", "Blue", "Green", "Yellow", "Pink", "Purple"]，那么“红色”的位置为0，“蓝色”的位置为1，“绿色”的位置为2，依此类推...

我假设您不太关心效率 - 即您没有处理包含 10 亿个项目的列表。

现在，要移动某个项目，我们的算法就是简单地将其从列表中删除，然后将其再次插入到正确的位置。假设我们再次有了该列表:

[“红色”、“蓝色”、“绿色”、“黄色”、“粉色”、“紫色”]

让我们考虑一些测试用例:

• 将位置 3 的项目移动到位置 0
• 将位置 3 的项目移动到位置 5
• 将位置 3 的项目移至位置 3(冗余情况)

在第一种情况下，我们将“黄色”移动到“红色”前面。所以像这样删除“黄色”

String removed = list.remove( 3 );

现在我们想将它插回位置 0。看起来我们可以这样做

list.add( 0 , removed );

很简单，对吧？删除给定索引处的元素，将其插入到所需索引处。让我们看看它是否适用于第二个测试用例。

在情况 2 中，我们想要将“Yellow”移动到位置 5。请注意，我们的列表中有六个元素，位置 5 对应于第六个位置(如果我们的数组索引从 0 开始)，因此“Yellow”将转到列表的末尾，在“紫色”之后。因此，我们再次删除“黄色”:

String removed = list.remove( 3 );

但是现在看，黄色之后的所有内容都向下移动了 1:

["Red, "Blue", "Green", "Pink", "Purple"]

方便起见，“Purple”的索引是4，如果我们在位置5处插入

list.add( 5 , removed );

我们得到

["Red, "Blue", "Green", "Pink", "Purple"]

看看这个算法是否适用于将黄色放在位置 3(冗余情况)处。

看起来我们的算法的工作原理如下:在给定位置删除，在目标位置插入。看起来我们可以编写这样的算法:

public void moveItem( int idxToMove , int targetIdx ) {
    String removed = list.remove( idxToMove );
    list.add( targetIdx , removed );
}

如果用户想要将列表中位置 3 向上 1 的项目移动，您可以调用

moveItem( 3 , 3+1 );

如果用户想要将列表中位置 3 的项目向下移动 1 个位置，您可以调用

moveItem( 3 , 3-1 );

如果用户想要将列表中位置 0 的项目向下移动 1 个位置，您会怎么做？

如果用户想要将位置 5 处的项目移动到位置 2 处的项目，您可以调用

moveItem( 5 , 2 );

现在您可以为 MapElementModel 的 ArrayList 实现此算法。如果您确实需要 MapElementModel 对象的 position 字段正确，则只需遍历 ArrayList 并更新它即可。 ArrayList 中元素的位置就是该元素的位置。

public void moveItem( int idxToMove , int targetIdx ) {
    //move the item as I did with Strings

    for ( int i=0 ; i<list.size() ; i++ ) {
        list.get( i ).position = i;
    }
}

如果您需要移动具有指定 id 的项目，您可以在 ArrayList 中找到它，然后移动它:

public void moveItemById( int itemId , int newPosition ) {
    int positionOfItem = -1;
    for ( int i=0 ; i<list.size() ; i++ ) {
        if ( list.get( i ).id == itemId ) {
            positionOfItem = i;
            break;
        }
    }
    if ( positionOfItem != -1 ) {
        moveItem( positionOfItem , newPosition );
    }
}