Как эффективнее найти количество пар, чем O(n^2)

Question

Как эффективнее найти количество пар, чем O(n^2)

Рейтинг: 1Ответов: 2Опубликовано: 27.04.2023

Задача: Дан массив натуральных чисел a. Найдите количество таких пар элементов (a_i, a_j), где abs(a_i − a_j) mod 200 == 0 и i < j

Я придумал такое решение:

// n - the length of numbers array
// numbers - the array of natural numbers

function getNumberOfGoodPairs(n, numbers) {    
    let count = 0;
    const remainders = new Map();
    
    for (const num of numbers) {
        const remainder = num % 100;
        const modifiedNum = (num - remainder) / 100;
        
        if (remainders.has(remainder)) {
            const nums = remainders.get(remainder);
            
            for (const num of nums) {
                if (Math.abs(num - modifiedNum) % 2 === 0) ++count;
            }
            
            nums.push(modifiedNum);
        } else {
            remainders.set(remainder, [modifiedNum]);
        }
    }
    
    return count;
}

Обозначения:

for (const arrayElement of array) - получает элементы из array один за другим и помещает этот элемент в arrayElement. Это то же самое, что:
```
for (let i = 0; i < array.length; ++i) {
  const arrayElement = array[i];
}
```
new Map() - это словарь
% - это mod
array.push(el) - добавляет el В конец array
remainders.get(remainder) - возвращает массив чисел, остаток которых равен remainder при делении на 100
remainders.set(remainder, [modifiedNum]) - добавляет в словарь новый ключ remainder и значение [modifiedNum]. [modifiedNum] - динамический массив с одним элементом modifiedNum

Если я прав, временная сложность в худшем случае будет O(n^2)

Пожалуйста, помогите мне оптимизировать этот алгоритм. Вы можете предоставить псевдокод для объяснения вашего алгоритма

алгоритм скорость оптимизация

Источник: Stack Overflow на русском

Answer 1

▲ 4Принят

Если я правильно понял условие, то с мапом или просто массивом на 200 элементов (b, заполненный нулями) задача решается за линейное время.

При обходе массива а вычисляете m=a%200 и добавляете к результату значение b[m], потом увеличиваете b[m]++

import random
a = [random.randint(1,10) for _ in range(6)]
b = [0]*4
cnt = 0
for x in a:
    m = x%4
    cnt += b[m]
    b[m]+=1
print(a)
print(cnt)

пара примеров

[4, 8, 10, 7, 9, 6]
2

[3, 9, 5, 6, 4, 5]
3

Answer 2

▲ 0

def get_mod_pairs(numbers: list[int], n: int) -> int:
    if n < 2:
        return 0
    count = 0
    
    result_dict = {}
    for i in numbers:
        result_dict.update(**{str(i%200): result_dict.get(str(i%200), 0) + 1})
    for d in result_dict:
        # 202, 402, 602, 802, 1002 // 2:1, 3:3, 4:6, 5: 10 ...
        # 1+2+3+4 = (4+1)*n/2
        cc = int(result_dict[d])
        if cc / 2 == 1:
            count += (cc) / 2
        if cc / 2 > 1:
            count += sum(range(1, cc))
    return int(count)

просто добавить счётчик остатков деления на 200, и всё.

А дальше количество комбинаций для каждого остатка - арифметическая прогрессия 1 .. n-1

Как эффективнее найти количество пар, чем O(n^2)

Ответы