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

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.

现在我们有两个测试场景:

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