алгоритм нахождения наименьшего различия в индексе равных чисел в массиве

Question

ли кто-нибудь есть идеи, как решить следующую проблему:

У нас есть массив, например, пусть это будет а = {1, 0, - 1, -2, -1, 0, 1, 2, 3, 4, 5, 1}.

То, что должен найти алгоритм, - это размер наименьшей разницы между индексами одних и тех же чисел. В этом примере (массив a) разность индексов единиц равна 6-0 = 0 и 11-6 = 5, разность индексов нулей равна 5-1 = 4, разность индексов минус равна 4-2 = 2 и т. Д. И алгоритм должен возвращать 2, потому что мы можем видеть, что это наименьшая разница индексов одинаковых чисел.

Есть ли способ решить эту проблему во временной сложности лучше, чем O (n^2)?

Answer 1

Несколько других ответов предлагают сортировку (элемент, индекс), которые могут быть выполнены в O (n * logn). Тем не менее, можно сделать лучше, всего лишь O (n) время. Нет необходимости сортировать массив или сохранять все пары (элемент, индекс), так как минимум можно найти с жадностью.

Пронумеруйте массив один раз и сохраните последний индекс каждого элемента в хеше.

int smallestDifference(int[] a) { 
    Map<Integer, Integer> lastIndex = new HashMap<>(); 
    int minDiff = Integer.MAX_VALUE; 
    for (int i = 0; i < a.length; i++) { 
     if (lastIndex.contains(a[i])) { 
      minDiff = Math.min(minDiff, i - lastIndex.get(a[i])); 
     } 
     lastIndex.put(a[i], i); 
    } 
    return minDiff; 
} 

Insert/получить из хэша O (1), так что дает O (N) для всего массива.

Answer 2

Следующая алго будет работать в O(nlogn)

1) Make a map of <int,vector<int> > . 
    2) Let the number be the key and the indexes be the vector. 
    3) sort the vector for all the keys. 
    4) Now find the minimum difference for all the difference between indices. 

Например: Для массива 1 2 3 2 1 3

1 -> [0,4] 
2 ->[1,3] 
3 -> [2,5] 

Здесь мы можем видеть, что 3-1 = 2 даст минимальную разницу в индексах.

Answer 3

Это написано на языке программирования Go.

func smallestIndexDifference(numbers []int) (mindiff int, exists bool) { 
    var prev map[int]int // The previous index where this number was found 
    for i, number := range numbers { 
    prevIndex, found := prev[number] 
    if found { 
     diff := i - prevDiff 
     if !exists || diff < mindiff { 
     exists, mindiff = true, diff 
     } 
    } 
    prev[number] = i 
    } 
    return 
} 

Это полностью непроверено, но если оно вообще работает, оно работает в O (n log n).

Answer 4

Сделайте vector<pair<int, int>>, в котором будут храниться значения исходного вектора с их соответствующими индексами. Для каждого значения v, чей индекс равен i, добавьте (v, i) к вектору.

Сортировка вектора (по значению, затем индекса).

Затем пройдите отсортированный вектор и найдите наименьшее (или самое большое, если хотите) расстояние между теми же ценными элементами.

Выполнение шагов O (n log n).

Answer 5

Во-первых, вы можете добавить индексы к вашей последовательности (O (N)):

> L = [1, 0, -1, -2, -1, 0, 1, 2, 3, 4, 5, 1]. 
[1,0,-1,-2,-1,0,1,2,3,4,5,1] 
> LI = lists:zip(L, lists:seq(1, length(L))). 
[{1,1}, 
{0,2}, 
{-1,3}, 
{-2,4}, 
{-1,5}, 
{0,6}, 
{1,7}, 
{2,8}, 
{3,9}, 
{4,10}, 
{5,11}, 
{1,12}] 

Затем отсортировать его (O (N журнал N)):

> LS = lists:sort(LI). 
[{-2,4}, 
{-1,3}, 
{-1,5}, 
{0,2}, 
{0,6}, 
{1,1}, 
{1,7}, 
{1,12}, 
{2,8}, 
{3,9}, 
{4,10}, 
{5,11}] 

Тогда вы найдете расстояния все же значений (O (N)):

> LD = (fun F([{X, P1}|[{X,P2}|_]=T]) -> [{P2-P1, X, {P1, P2}} | F(T)]; F([_|T]) -> F(T); F([]) -> [] end)(LS). 
[{2,-1,{3,5}},{4,0,{2,6}},{6,1,{1,7}},{5,1,{7,12}}] 

Тогда вы найдете минимальное расстояние (O (N)):

> lists:min(LD). 
{2,-1,{3,5}} 

Это означает минимальное расстояние 2 от значения -1 между позициями 3 и 5 и сложностью результата O (N log N). (Пример кода находится в Erlang.)