1

这是我的家庭作业问题的一部分。

我们得到了以下用于链排序的伪代码：

    define strandSort( L )
      result = []
      while len(L) > 0
        inorder = []
        remove first element of L, add it to inorder
        for each item i in L:
          if i >= last item in inorder
            remove i from L, add it to inorder
        result = merge(inorder,result)
      return result

我在程序中实现代码如下：

public List<Integer> strandSort(List<Integer> nums) {
    List<Integer> result = new ArrayList<Integer>();
    while(nums.size() > 0){
        List<Integer> inorder = new ArrayList<Integer>();
        int toAdd = nums.remove(0);
        inorder.add(toAdd);
        for(Integer i : nums){
            if (i >= inorder.get(0) ){
                toAdd = nums.remove((int)i);
                inorder.add(toAdd);
            }
        }
        result = merge(inorder, result);
    }
    return result;

但是，我在“for(Integer i : nums)”行遇到了越界错误。我相信我明白为什么会这样。我正在尝试遍历列表，同时从中删除元素。

我不确定如何解决它。如果我正确地实现了伪代码，我不相信它会遇到这样的错误。因此，我认为我没有正确实施它。

如果我有，在不破坏输入列表的情况下重新编写 strandSort 代码的最佳方法是什么？

（我为重复发布道歉，我在解释完之前不小心提交了问题！）

4

2 回答 2

0

toAdd = nums.remove((int)i); is your culprit.

From the JavaDoc:

E remove(int index) Removes the element at the specified position in this list (optional operation).

boolean remove(Object o) Removes the first occurrence of the specified element from this list, if it is present (optional operation).

It's confusing because you're casting an Integer to an int, causing the first version of remove() to be called. This causes your code to remove the element at i instead of i itself. Try getting rid of the explicit (int) cast.

于 2013-10-08T22:06:05.747 回答
0 
if (i >= inorder.get(0) ){

is not the same as 

if i >= last item in inorder

In the first case you are getting the first one, not the last one.

于 2013-10-08T22:06:16.587 回答