优化时间复杂度 - 奎因·麦克卢斯基

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 的长度存储为变量（而不是在每次迭代时重新计算它）。

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