Число пар, которые имеют по меньшей мере одну цифру

Ответ 1

Очень важно понять, какие переменные и какие здесь константы.

Число цифр является константой (10). То есть число всех наборов цифр (1024). Так же и число всех пар таких множеств (2 ²⁰ или примерно один миллион). Давайте воспользуемся этим.

Попробуйте и предварительно обработать вход в "эквивалентное" представление в структуре данных, размер которой постоянный (независимо от размера ввода). Что бы мы ни делали с этой постоянной структурой по размеру, это по определению постоянная операция времени, поэтому общее время работы асимптотически определяется только фазой предварительной обработки.

Структура данных

Создайте массив из 1024 целых чисел, каждый ведро (индекс), соответствующий набору цифр; мы хотим сохранить количество входных номеров, которые имеют именно тот набор цифр в каждом ковше.

Например, 3606 имеет цифры 0, 3 и 6, и поэтому он будет учитываться в ведре 2 ⁰ + 2 ³ + 2 ⁶= 73.

Алгоритм

Предварительная обработка очевидна. Возьмите следующую цифру (например, '3'), преобразуйте ее в ее значение (например, 3), теперь вычислите соответствующий бит (например, 1 << 3) и OR его в (пробную) индексную переменную bucket; разные цифры населяют разные биты, поэтому каждая комбинация цифр получает уникальное ведро, но мы избавились от любых повторяющихся цифр. Петля вроде этого, пока не встретите разделитель чисел; в этот момент индекс ведра является окончательным, и мы можем просто увеличить ведро, reset индекс ведра и пропустить до следующей цифры.

Что это. Остается только считать наших овец. К сожалению. Пары овец.

Сравните каждую ведро друг с другом ведром (но не с самим собой). Всякий раз, когда оба индекса имеют цифру (это можно определить с помощью оператора &), умножьте содержимое этих двух ведер вместе и добавьте продукт в глобально поддерживаемую сумму.

Сравните каждый ведро с самим собой и добавьте только x * (x - 1) / 2 в глобально поддерживаемую сумму, где x - это содержимое ведра.

Эта сумма является вашим результатом.

Производительность

Наихудший случай: O(n) где n - размер ввода.

Постоянные факторы также благоприятны. Нам понадобилось несколько инструкций (и доступ к ОЗУ) на каждую цифру или разделитель; и постоянная фаза рассматривает миллион пар ковша, проводя что-то вроде других небольших инструкций для каждой пары (без необходимости доступа к ОЗУ, структура данных очень компактна). Это молниеносно.

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

Более практичный программист заметит, что алгоритм является экспоненциальным по размеру алфавита. Нам повезло; если бы наши слова не состояли из цифр, а из произвольных символов, кроме разделителя, то наша была бы асимптотически линейным алгоритмом времени, но она была бы необычно медленной для любого ввода вообще, по сравнению с наивным алгоритмом, который мог бы легко хруст до мегабайта ввода за раз.

Ответ 2

создайте массив множеств, по одному для каждой цифры.

повторите свои номера и поместите каждое число в каждом наборе для цифр, которые он содержит.

итерация всех 10 наборов и объединение каждого элемента набора со всеми другими элементами в одном наборе. (или все другие элементы, большие, чем они есть, если вы не хотите (a, b) и (b, a) в вашем результате.

Я думаю, что это все еще O (n ^ 2), но его можно было бы легко парализовать с помощью подхода к соединению fork.

Обновление

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

anotherupdate

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

не работает Из комментариев:

Consider 1st pair in above questions test case (2837,2818), this will put first number in set containing digit 2 and 8 and same for 2818 now they are to be counted as one but counting in 2 and 8 will count it twice. I hope you understand what I am trying to say...

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

Ответ 3

Прежде всего, я замечаю, что положение обычных цифр не имеет значения.

В этом случае я рисую небольшой алгоритм с хэш-таблицей: form 10 bin, по одному для каждой цифры. Затем для каждого числа введите (однозначно) идентификатор номера в каждом бункете, соответствующий каждой цифре, которую он имеет. Эта операция O (n * k), k - количество цифр чисел. Наконец, чтобы сформировать все пары, возьмите пары чисел внутри каждого бина. Чтобы удалить, возможно, удвоения, расположите каждую пару (a, b) с помощью

Я думаю, что худшим случаем является фактически O (n ^ 2); на самом деле, я думаю, что этот шаг должен иметь сложность O (n ^ 2), поскольку вы хотите взять все пары (при max n * (n + 1)/2). Таким образом, окончательная сложность действительно квадратична.