对于 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:弄清楚我做错了什么。我不应该使用以前的枢轴点,而应该设置和更改我正在检查的区域的边界,并基于此创建新的枢轴。
为此使用 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 版本中工作。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)