java - Java 中的位置排序

Question

我不知道如何提出这个问题，但我认为一个例子可能会对解决这个问题大有帮助......所以这里是:

假设我有一个字符串数组:“Bob”“Alan”“Conrad”“Alice”“Alex”。

按字母顺序排序后，数组将变为:“Alan”“Alex”“Alice”“Bob”“Conrad”。

所以我们知道在这种情况下，从“B”开始的排序元素将位于位置号 3 之后。

现在我的问题是，java/android 中是否有一个内置函数可以让我在排序后知道一组结束而另一组开始(字符串在哪个位置从“A”转换到“B”)？

编辑:或者甚至可能结合使用两个不同的功能

Answer 1

我不熟悉任何可以执行此操作的内置函数。我怀疑是否有这样一个；部分是因为这看起来是一个相对不寻常的请求，部分是因为它在第二步中确实需要一个功能参数。 Guava(和其他库)提供 Predicate接口(interface)可以做到这一点，但标准库中没有类似的东西。

也就是说，您可以通过两个步骤非常简单地完成此操作:

1. 对集合进行排序。 (这是无法合理避免的；无论如何，您都必须检查每个元素并了解它们的相对顺序，因此您无法做得比排序所施加的 O(n) 行为更好)。
2. 遍历已排序的集合，根据谓词测试每个元素，直到找到第一个匹配/不匹配的元素。

对于后一步，如果您有二叉树之类的东西，并且您的测试适合 Comparator类似的界面，您可以更快地迭代树。但在一般情况下，真/假检查你不能做出这样的假设，所以你只需要走一遍。 (在完全一般的情况下，对于未排序的集合，您无论如何都会以线性时间执行操作，因此这不是什么大问题)。

不过，将其打包为您自己的库操作会很简单(假设您有 Function1 或 Transformer 或来自某个库的类似定义):

public <T> int indexOfPartition(Collection<T> coll, Function1<T, Boolean> pred, Comparator<T> cmp) {
    final Collection<T> sorted = Collections.sort(coll, cmp);
    final Iterator<T> iter = sorted.iterator();        
    int idx = 0;
    // Walk through the collection until we find an element that is "false"
    // under the predicate (i.e. not in the first partition).
    while (iter.hasNext() && pred(iter.next()) {
        idx++;
    }

    // TODO think about what you want when the collection is empty and/or when
    // the partition never changes (e.g. list of entirely strings starting
    // with "A")
    return idx;
}

您可以使用重载来修饰它，以传递默认的比较器和谓词等。

事实上，如果您希望谓词是动态的，那么不要使用 Function1<T, Boolean>你可以传入 Function1<T, ?>它将输入映射到任意输出对象 - 然后遍历字符串直到输出对象不同。在您的示例中，您可以传递一个函数来将字符串映射到它们的第一个字符，具体取决于您想要的是“当 B 开始时”或“当首字母从第一个元素开始变化时”。