Как эффективно рассчитать разницу между элементами массива и узнать, сколько различий меньше определенного значения?

Question

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

Я реализовал его, используя метод грубой силы:

for (int i = 0; i < n; i++) {
    int j = 0;
    while (j < n) {

        if (Math.abs(arr1[i] - arr1[j]) <= limit) {
            sum = sum + 1;
        }
        j++;
    }
}

Теперь,Я ищу оптимизированное решение, поскольку сложность времени здесь составляет O(n^2).Что было бы хорошим решением этой проблемы, если я хочу избежать двух циклов?

Answer 1

Если вам необходимо определить, отличается ли разница между каждой парой элементов в массиве <= limit, было бы полезно сначала отсортировать массив (O (NlogN)). </p>

Теперь для каждого элементаx в отсортированном массиве, вы должны найти длину диапазона элементов, имеющих значение между x - limit и x + limit.Это можно найти с помощью бинарного поиска (например, вызов Arrays.binarySearch(sortedArray, x - limit) и Arrays.binarySearch(sortedArray, x + limit)) за O(logN) время.Вы добавляете длину этого диапазона к общей сумме.

Поскольку вам придется повторять это действие для каждого элемента, общее время будет равно O (NlogN).

Наконец, так как вы будетесосчитайте каждую пару дважды, вы должны разделить результат на два.

Общее время выполнения будет O(NlogN) + O(NlogN) = O(NlogN).

Кстати, ваша текущая реализация кажется неверной:

1. Вы сравниваете каждый элемент с самим собой, который будет иметь дополнительное значение n с общей суммой.

2. Вы сравниваете каждую пару элементов дважды, поэтому каждая паракоторый достаточно близко, будет засчитан дважды.

РЕДАКТИРОВАТЬ: На самом деле, поскольку вместо подсчета каждой пары закрытия дважды, а затем деления на два, мы можем посчитать пары только один раз, если мы только посчитаемколичество элементов от array[i] (эксклюзив) до array[i] + limit (включительно).Это означает, что достаточно выполнить двоичный поиск один раз для каждого индекса.

Вот пример работы:

public static int comparePairs (int[] arr1, int limit) {
    int sum = 0;
    Arrays.sort (arr1);
    for (int i = 0; i < arr1.length - 1; i++) {
        int last = Arrays.binarySearch (arr1, arr1[i] + limit);
        if (last > 0) {
          sum += last - i;
        } else {
          sum += -last - i - 2;
        }
    }
    return sum;
}

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

Например, он возвращает 9 для массива {2,6,4,3,1,5} и ограничения 2 (пары: (1,2) (1,3) (2,3) (2,4) (3,4) (3,5) (4,5) (4,6) (5,6)).