9

在 Java 中，我有一个名为 TestClass 的类，它有一个名为 Name 的成员，它是一个字符串。我也有一个这种类型的 ArrayList，它已经按名称按字母顺序排序。我想要做的是找到放置TestClass 的新实例的最佳索引。到目前为止，我能想到的最好的方法是：

public static int findBestIndex(char entry, ArrayList<TestClass> list){
    int desiredIndex = -1;
    int oldPivot = list.size();
    int pivot = list.size()/2;
    do
    {
        char test = list.get(pivot).Name.charAt(0);
        if (test == entry)
        {
            desiredIndex = pivot;
        }
        else if (Math.abs(oldPivot - pivot) <= 1)
        {
            if (test < entry)
            {
                desiredIndex = pivot + 1;
            }
            else
            {
                desiredIndex = pivot - 1;
            }
        }
        else if (test < entry)
        {
            int tempPiv = pivot;
            pivot = oldPivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }
        else
        {
            int tempPiv = pivot;
            pivot = pivot - (oldPivot - pivot)/2;
            oldPivot = tempPiv;
        }

    } while (desiredIndex < 0);

    return desiredIndex;
}

本质上，将数组分成两半，检查您的值是否在该点之前、之后或之后。如果在之后，请检查数组的前半部分。否则，请检查下半场。然后，重复。我知道这种方法只测试第一个字符，但这很容易解决，与我的主要问题无关。对于某些情况，这种方法效果很好。对于大多数人来说，它的效果很糟糕。我假设它没有正确找到新的枢轴点，如果是这种情况，我将如何解决它？

编辑：为澄清起见，我将其用于库存系统，所以我不确定 LinkedList 是否合适。我使用 ArrayList 是因为它们对我来说更熟悉，因此在需要时更容易翻译成另一种语言（目前可能正在转移到 C#）。出于这个原因，我试图避免使用 Comparable 之类的东西，因为如果 C# 缺少它，我必须完全重新编写它。

编辑部分 Duex：弄清楚我做错了什么。我应该设置和更改我正在检查的区域的边界，而不是使用以前的枢轴点，并以此为基础创建新的枢轴点。

4

6 回答 6

9

为此使用 SortedSet（例如 TreeSet）可能不是一个好主意，因为 Set 不允许重复元素。如果您有重复的元素（即具有相同名称的 TestClass 实例），则应使用 List。将一个元素插入到已经排序的列表中很简单：

void insert(List<TestClass> list, TestClass element) {
    int index = Collections.binarySearch(list, element, Comparator.comparing(TestClass::getName));
    if (index < 0) {
        index = -index - 1;
    }
    list.add(index, element);
}

此代码需要 Java 8 或更高版本，但也可以重写以在较旧的 Java 版本中工作。

于 2018-08-17T10:06:16.407 回答
5

正如已经指出的，没有理由自己实现这个，简单的代码示例：



    class FooBar implements Comparable<FooBar> {

        String name;

        @Override
        public int compareTo(FooBar other) {
           return name.compareTo(other.name);
        }
    }

    TreeSet<FooBar> foobarSet = new TreeSet<>();
    FooBar f1;
    foobarSet.add(new FooBar("2"));
    foobarSet.add(f1 = new FooBar("1"));

    int index = foobarSet.headSet(f1).size();

（基于如何在 TreeSet 中查找元素的索引？）

于 2013-05-26T22:49:58.457 回答
1

我认为问题出在这段代码中：

else if (test < entry)
{
    int tempPiv = pivot;
    pivot = oldPivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}
else
{
    int tempPiv = pivot;
    pivot = pivot - (oldPivot - pivot)/2;
    oldPivot = tempPiv;
}

无论是 test < entry 还是 wether test > entry，您都在执行相同的操作。当您要搜索的项目位于数组的开头时，这将导致线性搜索。

我更喜欢使用（低和高）喜欢

high = list.size();
low = 0;

do {
   pivot = (high + low) / 2;
   if (test < entry) {
      low = pivot;
   } else if (test > entry) {
      high = pivot
   } else {
      ....
   }
} while ...;
于 2013-05-27T01:37:35.203 回答
1

您应该使用已经有秩序感的 PriorityQueue 之类的东西。插入到具有顺序感的集合中会自动将元素放置在正确的位置，并且时间最短（通常为 log(n) 或更短）。

如果您想在没有此功能的情况下进行任意插入，那么我建议您使用不需要使用或完全复制的 LinkedList 来插入单个项目，例如您当前拥有的 ArrayList。虽然为 LinkedList 找到正确的插入位置最多需要 O(n) 时间，但实际上它仍然比使用 log(n) 搜索 ArrayList 中的正确位置要快，但随后需要对其进行复制或排序然后。

此外，在链表中查找插入位置的代码要简单得多。

if (next != null && next.compareTo(insertElement) > 0){
    // You have the right location
}
于 2013-05-26T22:07:05.360 回答
1

可以使用其他数据结构来代替列表，如树、优先级队列等。

于 2013-05-26T22:26:10.597 回答
0

制作您自己的列表实现，并在您的 add 方法中有以下几行：

wrappedList.add(object);
Collections.sort(wrappedList);
于 2013-05-27T01:40:14.057 回答