Есть ли способ сравнить каждый элемент в массиве, используя один цикл?

Question

Мне нужно вывести наименьшую разницу между любыми двумя элементами массива int.

каждый элемент массива A меньше его длины.

1 <= A[i] <= A.length;

Я попробовал этот подход ниже в Java - Но это занимает больше 1 секунды, чтобы найти результаты, когда задан размер массива ~ 10 ^ 5.

Я думаю, что это может быть наивный подход. Есть ли способ, которым я могу оптимизировать это дальше? Можно ли это сделать за O(n) сложность времени?

static int findResult(int[] arr)
        {
                 int max =  Integer.MAX_VALUE;
                 HashSet<Integer> hs = new HashSet<Integer>();
                 for(int obj : arr)
                 {
                     hs.add(obj);
                 }
                if(hs.size()==1 )
                {
                    return 0;             // if all elements are same
                }
                 for(int i=0; i<arr.length; i++)
                 {  
                     for(int j=i+1; j<arr.length; j++)
                     {
                         int value = Math.abs(a[i]-a[j]);
                         if(value<max)
                         {
                            max = value;
                         }

                      }         
                }
        return max;  // returns the smallest positive difference
    }

Answer 1

Я предполагаю, что A являются целыми числами, в противном случае условие 1 <= A[i] <= A.len не имеет значения.

Тогда есть решение O(n) с использованием гистограммы.

1. объявляет массив счетчиков размером A.length;

2. подсчет кратностей элементов A;

3. отсканируйте эту гистограмму, чтобы найти ближайшие непустые ячейки.

---

Обратите внимание, что это решение предполагает, что рассматриваются только отличные от нуля различия. Если разница равна нулю, то ответ Виллема лучше.

Answer 2

(добавление к ответам выше)

Если вам нужно сделать это с O (1) лишним пробелом, вы можете использовать следующий трюк на входной последовательности A:

for a in A[1...n]:        // a is an element in A; A is 1-indexed; 1 <= a <= n
    if M < A[a % M]:
        return 0
    A[a % M] += M
return 1

Здесь M (> n) таково, что M + n не переполняется. Трюк можно легко модифицировать, чтобы использовать вместо него значение M, которое меньше -n.

Предостережения:

1. Требуется произвольный (т. Е. O (1)) доступ к элементам A.
2. Не подходит для кэша.

Answer 3

С 1 & le; x _i & le; n : O (n)

Так как для каждого x _i он содержит 1 & le; x _i & le; n , он удерживает его в силу принцип голубя , либо все значения существуют точно один раз , либо значение существует два или более раз .

В первом случае разница составляет 1 (для массива, превышающего 1 элемент), во втором случае результат равен 0, поскольку тогда есть два элемента, которые в точности равны.

Таким образом, мы можем перебирать массив и отслеживать числа. Если число уже существует один раз, мы возвращаем 0, в противном случае мы возвращаем 1, например:

// only if it holds that for all i, 1 <= arr[i] <= arr.length
static int findResult(int[] arr) {
    bool[] found = new bool[arr.length]
    for(int i = 0; i < arr.length; i++) {
        if(found[arr[i]-1]) {
            return 0;
        } else {
            found[arr[i]-1] = true;
        }
    }
    return 1;
}

Для случайного массива, который удовлетворяет условию с n элементами, в n! / N ⁿ случаев он вернет 1, а в других случаях он вернет 0, поэтому среднее значение по случайному вводу равно n! / n ⁿ . Когда n увеличивается, становится маловероятным, что "столкновений" нет, и поэтому, как говорит @ YvesDaoust , приближение 0 весьма вероятно.

Без 1 & le; x _i & le; n : O (n log n)

В случае, если мы снимаем ограничение, мы можем сначала отсортировать массив, и в этом случае мы перебираем последовательные элементы:

static int findResult(int[] arr) {
    Arrays.sort(arr);
    int dmin = arr[1] - arr[0];
    for(int i = 2; i < arr.length; i++) {
        int d = arr[i] - arr[i-1];
        if(d < dmin) {
            if(d == 0) {
                return 0;
            }
            dmin = d;
        }
    }
    return dmin;
}