Самые дальние равные элементы в массиве

Question

Предположим, у вас есть несортированный массив, как вы найдете 2 равных элемента, так что они самые дальние в массиве. Например, 8 7 3 4 7 5 3 9 3 7 9 0 ответ будет 7(9) - 7(1) = 8. Я думал о следующем

initialise max = 0
using hashing, store the elements along with its index
whenever there is a collision, compare the current index with the hashed one
if it is greater, set max = current index - hashed one and copy element along with index to some other location.

работает во времени - O (n) и в пространстве - O (n). Это правильно? Есть ли лучшее решение.

Answer 1

O (n) время выполнения и O (n) пространство, кажется оптимальным AFAIK.

Вот реализация Python:

#!/usr/bin/python
hashindex = {}

l = [8,7,3,4,7,5,3,9,3,7,9,0]

max_diff = 0
value = 0

for i in range(len(l)):
    indices = hashindex.get(l[i], None)
    if indices:
        hashindex[l[i]] = (indices[0], i)
    else:
        hashindex[l[i]] = (i, i)
    diff = hashindex[l[i]][1] - hashindex[l[i]][0]
    if diff > max_diff:
        max_diff = diff
        value = l[i]

print max_diff, value

Answer 2

Решение в obj-c. Должно быть O (N). Всего один проход по массиву.

//NSMutableArray *numbers = [[NSMutableArray alloc] initWithArray:@[@3,@2,@1,@7,@1,@2,@3,@6,@5,@4,@4,@5,@6,@7]];
//int solution = [self maxDistanceBetweenPairs:numbers];
//NSLog(@"%d", solution);

- (int)maxDistanceBetweenPairs:(NSMutableArray *)A {
    NSMutableDictionary *dictionary = [NSMutableDictionary dictionary];
    __block int max = 0;

    int i = 0;
    for (NSNumber *num in A) { 
        if ([dictionary objectForKey:num]) {
            int first = [[dictionary objectForKey:num] intValue];
            if (i - first > max) {
                max = i - first;
            }
        } else {
            [dictionary setObject:[NSNumber numberWithInt:i] forKey:num];
        }
        i++;
    }

    return max;
}

Answer 3

работает во времени - O (n) и в пространстве - O (n).Это правильно?

Да.

Есть ли лучшее решение?

Я очень сомневаюсь в этом.Реализация JavaScript:

function furthest(a) {
  const first= {};

  return a.reduce((longest, elt, idx) => {
    if (!(elt in first)) first[elt] = idx;
    return Math.max(longest, idx - first[elt]);
  }, Infinity);

}

Answer 4

Мое решение на Java: int [] testArr = {1,2,3,5,1,7,5,4,3,1,2,3,2,3};int maxLen = 0;int minidx = 0;int maxidx = 0;int numVal = testArr [0];int counter = 0;// Просто чтобы проверить, сколько раз входил внутри, если условие

for (int ii=0;ii<testArr.length-maxidx;ii++) {

    for (int jj=testArr.length-1;jj>=ii+maxidx;jj--){

        if(testArr[ii]==testArr[jj] /*&& maxLen<(jj-ii)*/){

            System.out.println(counter++);

            minidx = ii;
            maxidx = jj;
            maxLen = jj-ii;
            numVal = testArr[ii];

            break;

        }
    }
}

System.out.println(maxLen +" "+minidx+" "+maxidx+" "+numVal);

Answer 5

Вот мое представление о лучшем решении:

Поскольку эти два элемента будут находиться дальше друг от друга, я бы сделал цикл, который смотрит на начало массива и в конецМассив в то же время, и смотреть внутрь, первые соответствующие элементы, которые они найдут, будут дальше друг от друга.

Например:

8 7 3 4 7 5 3 9 3 7 9 0

First look at 8, 0, and store them in set A, and in set B respectively.
Look at 7, 9, and store them in the same sets fashion.
Look at 3, 7, and same as above. Now this 7 is already in the opposite set, A. 
Therefore they must be the farthest apart. Just calculate the distance between the the 7 elements. 

Теперь, когда я думаю об этом, вам просто нужно сделать какую-то проверку, чтобы убедиться, что самые дальние элементы теперь находятся внутри самого набора.

Таким образом, если любой из наборов имеет 1/3 всех элементов, вы также должны начать проверять, находится ли наибольшее расстояние внутри самого набора.

Answer 6

Я очень сомневаюсь, что это «правильный» ответ, но если бы мне дали эту проблему на работе, я бы сделал быструю сортировку по линиям сортировки по значению, а затем по индексу. Затем я бы прошел через мой упорядоченный массив и для каждого значения взял первый и последний индекс. Это станет кандидатом на максимальное расстояние. Каждый раз, когда я сталкивался с новым значением, я сравнивал его с моим текущим максимальным расстоянием, а затем сохранял только максимальное значение. Таким образом, время выполнения будет

сортировка + прогулка = всего N Log N + N = N Log N

Ex .: Значения в неупорядоченном массиве: 1,2,3,1,5,3,3,3

1,1,2,3,3,3,3,5 = значение 0,3,1,2,5,6,7,4 = индекс

1 = максимум 3-0 = 3

2 = х

3 = максимум 7-2 = 5

Макс. 5

Имейте в виду, что это, вероятно, НЕ ответ из учебника, но он все еще работает в N Log N, так что я бы использовал его на работе без всяких сомнений для чего-либо менее миллиона элементов.

Задумывались ли вы о других возможных ответах на проблему? Как насчет способов улучшить это?