上移、下移、指定位置

Question

我知道这应该看起来很初级，但出于某种原因，我无法完全理解可以解决此问题的算法，所以我将就此与社区联系。

我有一个 class 看起来像这样：

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，并且所有后续位置都需要相应更改。

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

最后，用户可以点击 "move down" 按钮并在列表中向下移动一个项目。同样，必须更新所有 MapElementModel.position 个字段。

有没有人有解决这个问题的好方法？感谢您的帮助！

Answer 1

最简单的解决方案是放弃使用 ArrayList 来存储它们。相反，请考虑使用 LinkedList。当您想要交换对象并通过从邻居到邻居遍历列表时，链表是一种非常好的数据结构。删除一个对象、添加一个对象或交换两个对象会自动更新所有 "indices"，因为您不再有索引，而只有与根项目的距离。

但是，如果您确实想继续使用 ArrayList 实现，那么是的，您是对的。您最有可能遇到的问题是您必须遍历必须更改的项目，并将索引 i 处的项目换成索引 i-1 处的项目。执行此操作时，您将创建大量临时对象以处理每次交换。

您的代码看起来笨拙而且速度很慢（假设您正在进行大量交换），但这是您使用 ArrayList 的代价。好处是您可以直接通过索引 i 访问项目，而不必从根对象开始循环遍历 LinkedList 中的 i 项目。

Answer 2

你说，"The list is sorted based on MapElementModel.position"，所以我的回答将以此为基础。如果它是根据 MapElementModel.id 排序的，这将是一个不同的算法。

将 ArrayList 视为您订购的物品集合。而不是 "storing" 在 MapElementModel 中的位置，只需让 ArrayList 中元素的索引作为其位置。比如你的ArrayList有元素["Red", "Blue", "Green", "Yellow", "Pink", "Purple"]，那么"Red"的位置是0，"Blue"的位置是1，[=82=的位置]为2，以此类推...

我假设您不太关心效率 - 即您处理的不是 10 亿项的列表。

现在，要移动一个项目，我们的算法是简单地将其从列表中删除并再次插入到正确的位置。假设我们再次获得列表：

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

让我们考虑几个测试用例：

将位置 3 的项目移动到位置 0
将位置 3 的项目移动到位置 5
将位置 3 的项目移动到位置 3（多余的情况）

第一种情况，我们把"Yellow"移到"Red"前面。所以像这样删除 "Yellow"

String removed = list.remove( 3 );

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

list.add( 0 , removed );

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

在情况2中，我们要将"Yellow"移动到位置5。注意我们的列表中有六个元素，位置5对应第六个位置（如果我们的数组索引从0开始），所以 "Yellow" 会到列表的末尾，在 "Purple." 之后所以，我们再次删除 "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的item移动到位置2的item，你调用

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 );
    }
}

Answer 3

为什么不实现一些通用的？在这种情况下，我会使用 LinkedList，但您可以改为扩展 ArrayList。

public class MovableList<T> extends LinkedList<T> {

    public MovableList() {
        super();
    }

    public MovableList(Collection<T> c) {
        super(c);
    }

    /** Returns removed elements */
    public Collection<T> remove(int[] indexes) {
        Collection<T> removeList=new ArrayList(indexes.length);
        for(int index: indexes){
            removeList.add(get(index));
        }
        removeAll(removeList);
        return removeList;
    }

    /** Returns inserted elements */
    public Collection<T> insert(List<T> from, int[] indexes, int position) {
        Collection<T> insertList=new ArrayList(indexes.length);
        Arrays.sort(indexes);
        for(int index: indexes){
            insertList.add(from.get(index));
        }
        addAll(position, insertList);
        return insertList;
    }

    public void moveTo(int[] indexes, int position) {
        Arrays.sort(indexes);
        addAll(position, remove(indexes));
    }

}

Answer 4

public void shift(List<String> currentList, String element, int places) {
    int fromPos = -1;
    int toPos = 0; 

    if (places != 0) {

        //Creates a new list
        List<String> newList = new ArrayList<>();

        // get curren position
        fromPos = currentList.indexOf(element);

        if (fromPos >= 0) {
            // If was found, calculates new position
            toPos = fromPos - places;               

            if (toPos >= 0 && toPos < currentList.size()) {
                // new position is in range

                if (places > 0) {
                    //move forward
                    if (toPos == 0) {
                        // move at the head
                        newList.offer(element);
                        newList.addAll(currentList.subList(0, fromPos));
                        newList.addAll(currentList.subList(fromPos + 1, currentList.size()));
                    } else {
                        // some places forward
                        newList.addAll(currentList.subList(0, toPos));
                        newList.offer(element);
                        newList.addAll(currentList.subList(toPos, fromPos));
                        newList.addAll(currentList.subList(fromPos + 1, currentList.size()));
                    }                       
                } else {
                    //move backward
                    if (toPos == (currentList.size() - 1)) {
                        // move at the end of the list
                        newList.addAll(currentList.subList(0, fromPos));
                        newList.addAll(currentList.subList(fromPos + 1, currentList.size()));
                        newList.offer(element);
                    } else {
                        // move some places backward
                        newList.addAll(currentList.subList(0, fromPos));
                        newList.addAll(currentList.subList(fromPos + 1, toPos + 1));
                        newList.offer(element);
                        newList.addAll(currentList.subList(toPos + 1, currentList.size()));
                    }                       
                }

                // replace old list
                currentList = newList;                      
                newList = null;                 

            }
        }           

    }
}

Answer 5

您真正的问题是您拥有必须保持同步的冗余信息。 "position" 存储在两个地方：

在List中，凭借哪个列表元素包含对象
在 MapElementModel 本身，在 position 字段中

您应该考虑摆脱其中之一，以避免需要使它们保持同步。 MapElementModel 真的需要知道自己在包含它的列表中的位置吗？

如果您真的必须同时保留两者，则需要：

从列表中删除元素
在新位置插入元素
使用新位置更新元素的 position 字段
更新位置也已更改的所有元素的 position 字段

所以：

  // remove the element from the list
  oldPosition = element.getPosition();
  list.remove(oldPosition);

  // insert the element in its new position
  list.add(newPosition, element);

  // the elements with new positions are those with positions
  // greater than or equal to the new position or the old position,
  // whichever is lower

  for(int i = Math.min(newPosition,oldPosition); i<list.size(); i++) {
       list.get(i).setPosition(i);
  }

这不是特别有效，但这是您选择的数据结构的限制。

Answer 6

您想要的是 ArrayList 中非常昂贵的操作。它需要将列表开头和 C 位置之间的每个元素向下移动一个。

但是，如果你真的想这样做：

int index = url.indexOf(itemToMove);
url.remove(index);
url.add(0, itemToMove);

如果这对您来说是一个频繁的操作，而随机访问的频率相当低，您可以考虑切换到另一个 List 实现，例如 LinkedList。如果您非常在意元素的顺序，您还应该考虑列表是否是正确的数据结构。

另一方面，如果只是移动一行

向上：

int index = items.indexOf(myObject);
Collections.swap(items, index, Math.max (0, index - 1));

唐：

int index = items.indexOf(myObject);
Collections.swap(items, index, Math.min (items.size () - 1, index + 1));

上移、下移、指定位置

Move up, move down, specify position

java

sorting

collections

list