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

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);

如何在时间复杂度方面做得更好？

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)

c 左侧的项目必须是 d , 否则我们可以取 a或 b索引并有一个改进的解决方案。 d 右边的项目必须是 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;
    }