如何高效地找到最小的正整数？

Question

我正在阅读一段文本，想要找到第一句话的结尾，也就是字符串中第一个'.'、'?'或'!'的位置。以下是我的Java代码：

int next = -1;
int nextQ = text.indexOf("? ");
int nextE = text.indexOf("! ");
int nextDot = text.indexOf(". ");
if (nextDot > 0) {
    next = nextDot;
    if (nextQ > 0){
        if (nextQ < next) {next = nextQ;}
        if (nextE > 0) {
            if (nextE < next) {next = nextE;}
        }
    } else if (nextE > 0){
        if (nextE < next) {next = nextE;}
    }
} else if (nextQ > 0){
    next = nextQ;
    if (nextE > 0 && nextE < next){next = nextE;}
} else if (nextE > 0) { next = nextE;}

我相信这个代码是有效的，但总共有10个if语句，看起来不太整洁。我可能想要添加更多的句子分隔符，但我认为这种方法不够灵活。有没有更好的方法来实现同样的效果？有没有更短的方法来达到同样的结果？...还是我应该尝试一些其他编程语言来解决这种问题？哪一个呢？

- Miro Lehtonen

---

“我应该尝试其他编程语言来解决这种问题吗？”哈哈，不要因为卡住了就换语言。 - Dici

return 1 是什么意思？这是我对标题的理解。 - maaartinus

Answer 1

我建议使用正则表达式一次性搜索所有这些分隔符。

String text = <TEXT>;
int next;
Pattern p = Pattern.compile("\\? |! |\\. ");
Matcher m = p.matcher(text);
if (m.find()) {
   int next = m.start();
} else next = -1;

您可以更改正则表达式以调整匹配的内容。例如，建议您不要仅在定界符后面要求一个空格，而是要求任何空白字符，这样换行符或制表符也可以使用。代码如下："\\?\\s|!\\s|\\.\\s"。您可以类似地添加额外的分隔符，并通过一些额外的工作来检测触发了哪个分隔符。

Java正则表达式Pattern类的文档在此处，有用的教程在此处。

- gandaliter

---

在模式读取“\? |! |\.”之后，它可以工作。我还不明白为什么有些字符必须要转义两次，但我会继续阅读的。我以前甚至不知道正则表达式类存在。谢谢！ - Miro Lehtonen

哦，对不起。我忘记了在Java字符串中需要转义反斜杠！我已经编辑了答案以反映这一点。 - gandaliter

Answer 2

使用方法来保持DRY（不重复原则）：

int firstDelimiterIndex(String s) {
    return minIndex(s.indexOf(". "), minIndex(s.indexOf("? "), s.indexOf("! ")));
}

int minIndex(int a, int b) {
    if (a == -1) return b;
    if (b == -1) return a;
    return Math.min(a, b);
}

或者选择更快的算法：

for (int i = 0; i < s.length; i++) {
    switch (s.charAt(i)) {
    case '.':
    case '?':
    case '!':
        if (i + 1 < s.length() && s.charAt(i + 1) == ' ') 
            return i;
    }
}

- meriton

---

你的第二个算法忽略了空白。 - maaartinus

Answer 3

使用Math.min和一些小修改。

首先，将-1转换为大正整数：

int largeMinusOne(int a)
{
    return a==-1 ? 9999999 : a;
}

int nextQ = largeMinusOne(text.indexOf("? "));
int nextE = largeMinusOne(...);
int nextDot = largeMinuseOne(...);

现在：

int next = Math.min(Math.min(nextQ, nextE), nextDot);

- zmbq

---

谢谢！看起来很不错，除了完全找不到分隔符的情况（文件结尾、亚洲语言等）。但如果我在结尾测试9999999，它可能仍然有效。 - Miro Lehtonen

嗯，是的，如果没有分隔符，结果就是9999999。 - zmbq

Answer 4

您可能只想过滤掉那些不好的值（即 == -1）（Java 8）：

int nextQ = text.indexOf("? ");
int nextE = text.indexOf("! ");
int nextDot = text.indexOf(". ");
OptionalInt res = IntStream.of(nextQ, nextE, nextDot).filter(i -> i != -1).min();
if (res.isPresent())
    // ok, using res.get()
else
    // none of these substrings found

这更像是一个笑话而不是真正的答案，在现实生活中应该使用gandaliter的答案。

- Dmitry Ginzburg

---

谢谢你的“玩笑” :) 也许我以后会需要这些新类，一旦我弄清楚它们在哪里更好，正则表达式包也更好。 - Miro Lehtonen

Answer 5

我建议只需逐个字符遍历字符串，并在遇到任何这些字符时停止。你现在的做法要低效得多。

- user207421