数组中两个不同元素之间的最大距离

Question

我有一个问题，需要找到数组中两个不同元素之间的最大距离。

例如：给定数组4,6,2,2,6,6,4，该方法应返回5作为最大距离。

我能够使用两个for循环解决这个问题，但这并不是一种优化的解决方案。我正在试图通过在单个for循环中完成它来进行优化。

这是我的当前解决方案：

int [] A = {4,6,2,2,6,6,4};
int N = A.length;
int result = 0;

for (int i = 0; i < N; i++){
    for (int j = i; j < N; j++) {
        if(A[i] != A[j]){
            result = Math.max(result, j - i);
        }
    }
}

// tried below code but it is not efficient
//      for (int i = 0; i < N; i++){
//          
//          if(A[N-1] != A[i]){
//              result = Math.max(result, N-1-i);
//          }
//      }

System.out.println(result);

如何在时间复杂度方面改进这个方法？

- roger_that

---

怎么样使用两个数组，原始数组A和反转数组R，对于A中的每个元素，在A和R中获取indexOf(element)。 - Sinstein

Answer 1

只需要简单的循环（不要嵌套），但需要考虑两种情况：要么是最佳结果，要么不是。

  4,6,2,2,6,6,4
    ^         ^ - moving first

或者

  4,6,2,2,6,6,4
  ^         ^   - moving last

例如：[4, 2, 4, 4, 4]，应该先移动才能得到答案；而在[4, 4, 4, 2, 4]的情况下，则应该最后移动才是最佳选择。

  int first = 0;
  int last = A.length - 1;

  // 1st case: moving "first"
  while (first < last) {
    if (A[first] == A[last])
      first++;
    else
      break;
  }

  int diff1 = last - first;

  first = 0;
  last = A.length - 1;

  // 2nd case: moving "last"
  while (first < last) {
    if (A[first] == A[last])
      last--;
    else
      break;
  }

  int diff2 = last - first;

  // result is the max between two cases
  int result = diff1 > diff2
    ? diff1
    : diff2;

因此我们具有O(N)的时间复杂度。

编辑: 让我们证明至少一个索引为0或length - 1。让我们通过反证法来证明。假设我们有这样一个解决方案：

  a, b, c, .... d, e, f, g
        ^ ..... ^  <- solution indexes (no borders)

左侧的项目必须是d，否则我们可以选择a或b索引并获得一个改进的解决方案。右侧的项目必须是c，否则我们可以再次将最后一个索引向右推动以获得更好的解决方案。所以我们有：

  d, d, c .... d, c, c, c
        ^ .... ^  <- solution indexes 

现在，由于 d <> c （c..d 是一个解），我们可以将这个解 改进 成为：

  d, d, c .... d, c, c, c
        ^ .... ^           <- solution indexes 
  ^       ....          ^  <- better solution

我们有一个“矛盾”（所谓的解决方案并不是一个好选择），这就是为什么至少一个索引必须是0或length - 1。

现在我们有2个场景需要测试：

  a, b, ..... y, z
     ^  ......   ^ <- moving first
  ^  ......   ^    <- moving last

我们可以将这两个条件结合到一个 if 语句中，然后只需要一个循环：

  int result = 0;

  for (int i = 0; i < A.length; ++i)
    if (A[i] != A[A.length - 1] || A[0] != A[A.length - 1 - i]) {
      result = A.length - i - 1;

      break;
    }

- Dmitry Bychenko

---

你能解释一下为什么我们需要移动到最后吗？ - roger_that

@roger_that：非常同意，对于我第一次简短的回复感到抱歉。已添加示例和证明。 - Dmitry Bychenko

谢谢您的证明。我也是这么想的。但我觉得代码可以简化一下。您能看一下我的答案吗？ - thebenman

Answer 2

这可以在一个循环中完成。

考虑以下内容。

从索引i开始的最大差异可以是起始元素和i之间，也可以是i和最后一个元素之间。

int main() {
    vector<int> v {4, 6, 2, 2, 6, 6, 4};
    int start = 0, end = v.size() -1;
    int result = 0;
    for(int i=0; i< v.size(); ++i)
    {
        if(v[i] != v[start])
        {
            result = max(result, i);
        }
        if(v[i] != v[end])
        {
            result = max(result, end - i);
        }
    }
    return result;
}

我们能够实现 O(N) 算法的原因是：

考虑数组 v = [4, 4, 2, 3, 4, 4]。

在索引 i = 0 处，我们检查是否可以找到最大可能的距离，即与最后一个元素相同，但由于它们相同，我们不能将其考虑在内。

对于这个数组，在 i = 0 处，最大可能的答案是5。

[4, 4, 2, 3, 4, 4]
 ^

在 i = 1 时，我们再次检查数组的两端是否相同，因此我们继续执行。

真正的节省在于我们不必检查从 i = 0 开始的每个其他条目。

因此，在 i = 2 时，我们发现可以通过使用数组的结尾来获得最大值。

[4, 4, 2, 3, 4, 4]
 ^     ^        ^
start  i       end

这与保持start不变并保持一个运行循环相同。

- thebenman

---

非常不错的实现方式；我宁愿坚持使用问题中提到的 数组 A。 - Dmitry Bychenko

@DmitryBychenko 谢谢。实际上，我是指用一个循环而不是两个 while 循环来完成这个任务。 - thebenman

如果你比较 v[i] != v[end] || v[start] != v[end - i]，你可以在第一次不同的时候返回 - 或者当 v.size()/2 <= i 时：所有元素都相等。 - greybeard