1

我有一组作为前缀的元素。我必须以这样一种方式编写 Java 方法，即每当它获得输入时，验证它属于哪个前缀，如果它与任何前缀匹配，则返回 true 或 false。元素是

1900
1901
1902
1903
17082

输入将是

1900123445
1901334455
1800777777
...

我可以使用哪种数据结构，以免影响性能。因为一次输入的数字会高达5000万。

任何人都可以帮助我吗？提前致谢。

4

5 回答 5

2

如果可能，测试这些方法中的每一个，看看哪种方法在上下文中最快。这可能取决于多种因素，我无法真正预测哪一个在您的特定用例中最有效。

选项 0（如果您的前缀很少，请使用此选项）

最简单的选择：将您的前缀存储在一个链接列表中，并使用input.startsWith(prefix). 无聊的。

选项 1（如果有非数字前缀，请使用此选项）

设k为最小前缀长度。使用 a HashMap，其中键是每个前缀的第一个k数字，项目是包含每个前缀其余部分的链表。

例如，假设您有前缀abcd、abce和xyz。然后，您将存储以下内容：

  • "abc"--> ("d","e")，其中("d","e")是包含元素的链表"d"和"e"
  • "xyz"--> ("")（""空字符串在哪里）。

调用此 map prefixes，并使用以下代码确定前缀是否正确：

public boolean correctPrefix(String input){
    LinkedList check = prefix.get(input.substring(0,k))
    if (check != null){
        for (String n : check){
            if (input.substring(k).startsWith(check)) return true;
        }
    return false;
}

我不知道它是否足够快以满足您的目的，尽管您还没有确切地告诉我们这些是什么；不过，我不知道Java中有什么更快的东西。

选项 2（如果所有前缀都是数字，或者您使用的是 SE7，则使用此选项）

使用switch声明。或者更确切地说，使用多个 switch 语句，一个用于每个可能的前缀长度。例如，假设您有前缀1901、1902和20050：

public boolean correctPrefix(String input){
    int pVal;
    pVal = Integer.parseInt(input.substring(0,4));
    switch (pval){
    case 1901: return true;
    case 1902: return true;
    }
    pVal = Integer.parseInt(input.substring(0,5));
    switch (pval){
    case 20050: return true;
    }
    return false;
}

这将是更多的代码，但我怀疑假设您有足够的前缀长度相同，它会更快。请注意，如果一个switch语句没有很多可能的情况，它实际上不会被编译为一个真正的switch语句，而是作为一系列if/else块，这将导致它相当慢。不过，您应该对此做一些处理，看看您会得到什么；加入一些虚假陈述可能是值得case [wrongprefix]: return false;的，因为信不信由你，它们实际上可以加快速度。

实际上，从 SE7 开始，switch 语句可以与字符串一起使用。我不确定这有多有效，但这是一种选择。

或者，如果您使用的是 SE7 之前的东西，您可以尝试....

选项 3（如何作弊）

您实际上可以将基数传递给parseInt，这意味着如果您的前缀中有字母但它们不区分大小写，您可以使用它Integer.parseInt(input.substring(0,4),36)来获取一个有效的整数值，然后您可以将其与switch.

于 2013-05-02T06:34:28.480 回答
1

您最好的选择是将前缀存储在 HashMap 中，并且值应该是一个链表。我假设相同的前缀可以用各种数字标记，例如 19011234 190123444。

于 2013-05-02T06:34:36.420 回答
1

前缀长度相同吗？

如果是这样，您可以散列所有前缀。

当您遇到新输入时，您将提取前 x 个数字。

您将寻找散列中前 x 位的存在 - 如果散列设计良好，则为 O(1) 操作。

于 2013-05-02T06:35:54.647 回答
1

如果你只有（相对）小的整数，你可以使用一个稀疏的布尔数组，你的前缀将作为索引。

或者，aHashSet将是一个不错的选择。

于 2013-05-02T06:36:15.523 回答
1

创建一个HashSet并在其中添加这 4 个值。然后解析您的输入值以获取前四个整数并调用 HashSetcontains()方法，该方法将返回真/假。

于 2013-05-02T06:36:37.963 回答