优化时间复杂度- Quinn McClusky

Question

我实现了Quinn McClusky逻辑最小化，现在正在尝试优化这段代码：

public int[] differsMaxOneChar(String a, String b) {
    debug.println("Comparing " + a + " to " + b);
    int[] returnValue = {1, 0};
    boolean differs = false;
    for (int i = 0; i < a.length(); i++) {
        if (!(a.charAt(i) == b.charAt(i))) {
            if (differs) {
                returnValue[0] = 0;
                break;
            } else {
                differs = true;
                returnValue[1] = i;
            }
        }
    }
    return returnValue;
}

在这方面的任何帮助都将非常感谢。

字符串a和b的长度总是相同的。方法检查它们是否恰好在一个位置不同。A和b由'0‘、'1’和'X‘组成。没别的了。

Answer 1

在O时间复杂度方面，你已经达到了O(n)，这对于这个问题来说是尽可能好的。只有一些小方法(不会影响O复杂度)可以优化，比如将a的长度存储为变量(而不是在每次迭代中重新计算它)。

此外，您的函数名称表明您正在检查它是否最多相差一个字符，但在您的描述中，您说的是“恰好一个”位置。你想要做的是什么？