优化时间复杂度 - 奎因McClusky

Question

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

此外，您的函数名称暗示你正在检查它是否至多有一个字符不同，但是在你的描述中你说的是“完全一个”的位置。你想要做什么？