6

Дан массив цифр (любой длины) и число.

Как проверить, что число содержит все цифры из массива?

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

Можете предложить более быстрый способ ?

2
  • 1
    Всего цифр 10. Что может быть громоздкого в алгоритме?
    – Max ZS
    28 фев 2016 в 20:52
  • 1
    да, но цифры могут повторяться, и таким образом размерность массива может быть любой.
    – Drylozav
    28 фев 2016 в 21:16

8 ответов 8

5
  1. Создаем массив из 10 элементов, равных нулю. Назовем его CNT.
  2. Заведем числовую переменную K=1
  3. Бежим по входному массиву, увеличиваем CNT[цифра] на 1. Умножаем K на 10.
  4. Закончили читать цифры. Делим K на 10 (т.к. один лишний раз умножили)
  5. Убеждаемся, что K<=ЧИСЛО и K*10>ЧИСЛО(что бы лишней работы не делать). Т.е. проверяем, что число содержит столько же разрядов, сколько цифр в массиве.
  6. В цикле делим ЧИСЛО на 10, вычитаем 1 из CNT[остаток-от-деления]. Если элемент в CNT стал меньше 0 - число не совпадает с массивом.
  7. Так как мы знаем, что разрядность ЧИСЛА была равна длине массива и ни один из элементов CNT не стал отрицательным - значит все цифры были в нужном количестве !

Итого для работы нам надо один раз пройти по входному массиву и один раз по разрядам числа. Т.е. сложность порядка O(2n). В отличие от поиска каждой отдельной цифры перебором массива (даже если это встроенная функция), где сложность O(n*n)

1
  • хорошо, только один нюанс, скорее всего входное число будет строкой и выполнить сравнение будет проблематично. Длинную арифметику в вопросе не упоминали. Но ваш ответ легко перестраивается под строки сохраняя линейную сложность.
    – rdorn
    28 фев 2016 в 23:10
1

Можно перевести число и цифры в строку/символы. И выполнить нужное количество раз поиск по строке.

1

Можно выделить каждый разряд (видимо, десятичный - остаток от деления на 10) и проверить, входят ли получившиеся цифры в заданный массив.

1
  • Как раз делал таким способом.
    – Drylozav
    28 фев 2016 в 21:26
1

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

Теперь, ваш массив цифр нужно превратить в множество (например, завести пустое множество и добавлять цифры по одной). Набор цифр числа проще всего получить, переведя число в строковое представление и отбросив возможные «лишние» символы (например, минус). Строек можно легко разобрать на символы и упаковать во множество.

После получения двух множеств вопрос становится тривиальным: операция проверки вхождения обычно вам дана языком.

4
  • на множествах появится зависимость от реализации множества в языке, и можно попасть на то же квадратичное решение, только запакованное в типы и операции для множеств
    – rdorn
    28 фев 2016 в 23:12
  • @rdorn: Я больше заботился о семантике, а не об эффективности. В конце-концов, максимальная длина числа типа int меньше 20 (десятичных) цифр, так что любое решение всё равно O(1).
    – VladD
    29 фев 2016 в 0:37
  • так то конечно, но по формулировке задачка больно похожа на учебную или олимпиадную начального уровня. Поэтому число запросто может оказаться N-значным, и крутись как хочешь.
    – rdorn
    29 фев 2016 в 0:53
  • @rdorn: Вызов принят! :) Окей, но во множестве всё равно не более десяти элементов, так что сравнение множеств всё равно O(1). Создание множества при фиксированном N по идее тоже O(1). Единственное, что потенциально может быть квадратичным при плохой реализации множества — создание множества из массива цифр, т. к. на длину массива ограничений не было.
    – VladD
    29 фев 2016 в 1:21
1

Пример на PHP:

function check($your_array, $your_number) {

    while ((int) $your_number !== 0) {

        $current = $your_number % 10;
        $your_number /= 10;

        if (!in_array($current, $your_array)) {
            return false;
        }
    }

    return true;
}

Примеры использования:

if (check(array(1, 2, 3, 4), 1234)) {
    echo 'success';
} else {
    echo 'fail';
}

Результат: success

if (check(array(1, 2, 3, 4), 123)) {
    echo 'success';
} else {
    echo 'fail';
}

Результат: success

if (check(array(1, 2, 3, 4), 125)) {
    echo 'success';
} else {
    echo 'fail';
}

Результат: fail

ВАЖНО: проверяется именно то, что все цифры есть в массиве. В массиве могут быть цифры, которых нет в числе. Обратное -- неверно.

UPDATE

А вот строгая проверка. Т.е. что все цифры массива есть в числе.

function check_strictly(& $your_array, $your_number) {

while ((int) $your_number !== 0) {

    $current = $your_number % 10;
    $your_number /= 10;

    foreach ($your_array as $key => $value) {
        if ($value == $current) {
            unset($your_array[$key]);
        }
    }

    return count($your_array) === 0;
}

$your_array = array(5, 1, 2, 3, 4, 1, 2, 3);

if (check_strictly($your_array, 1234)) {
    echo 'success';
} else {
    echo 'fail';
}

Результат: fail

3
  • Спасибо, делал именно таким образом. Буду проверять, почему у меня не верно. Скажите, а если речь идет о проверке не только состоит ли число из массива цифр, но и содержит ли число все цифры массива, как в этом случае можно решить задачу ?
    – Drylozav
    28 фев 2016 в 21:24
  • @Drylozav, пожайлуста. Можно удалять элементы из массива, и посмотреть потом если в массиве элементы.
    – sleeper
    28 фев 2016 в 21:27
  • Благодарен Вам. Идею с удалением я как то не додумался рассмотреть.
    – Drylozav
    28 фев 2016 в 21:53
1

Алгоритм может быть такой:

  • 0). Получаем число и массив цифр.
  • 1). Создаём массив цифр из заданного числа.
  • 2). Для этих двух массивов создаём хеши, которые содержат количество вхождений заданной цифры.
  • 3). Затем попарно сравниваем значения этих хешей, где ключом является число от 0 до 9.
  • 4). Если сравнение не сработало, значит заданное число не удовлетворяет условию задачи.

Реализация на perl

sub check {
    # Шаг 0.
    my $number     = shift;
    my $digits_arr = shift;

    # Шаг 0.1: (опциональный - так как из условия не ясно, 
    # имеем ли мы дело только с натуральными числами или нет)
    #
    # Поэтому предварительно уберём лишний мусор из числа.
    # Например: -0.234 => 0234; -234.92 => 23492
    $number =~ s/[^\d]//ig;  

    # Шаг 1.
    my @number_digits = unpack('(a)*', $number);

    my %n;
    my %d;

    # Шаг 2.
    $n{$_}++ for @number_digits;
    $d{$_}++ for @{ $digits_arr };

    # Шаги 3 и 4.
    ($n{$_}//=0) == ($d{$_}//=0) or return for 0..9;

    return 1;
}

print check(-22.34999, [9,9,2,3,4,2,9]);
1

UPD

Проверка через replace

Для PHP есть решения "в оба конца", нечувствительные к повторам цифр в массиве цифр $digits и в числе $number, которые используют функции preg_replace() и str_replace().

Если:

  • число $number использовать как шаблон (строка "/[$number]/");
  • в качестве строки замены взять пустую строку;
  • массив цифр склеить в обрабатываемую строку (функция implode($digits)),

то функция preg_replace() удалит в обрабатываемой строке все символы шаблона,
т.е. при наличии всех цифр из массива цифр в числе на выходе будет пустая строка.

Если же

  • использовать массив $digit в качестве массива поиска;
  • в качестве строки замены использовать пустую строку;
  • вместо обрабатываемой строки использовать число $number,

то функция str_replace() удалит все цифры массива поиска из обрабатываемой строки,
т.е. при наличии в массиве цифр всех цифр числа на выходе будет пустая строка.

Такой подход приводит к короткому и эффективному коду.

Проверка с переводом числа в массив цифр

Поскольку количество цифр ограничено, то разница в программной сложности алгоритмов сводится к коэффициенту 10.
За этот коэффициент можно побороться так:

  • с помощью функции str_split() или sscanf() преобразовать число в массив цифр;
  • упорядочить массивы и выбросить повторы;
  • сравнить массивы в параллельном проходе (если в одном из массивов нашлась меньшая цифра, то он точно не подмножество другого).

Однако тесты показали проигрыш в производительности.

Программа:

define("N", 100000);
define("M", 11);
define("PR", 1);

function print_digits($text, $digits){
    print "$text [ ";
    foreach($digits as $dig){
        print"$dig ";
    }
    print "]";
}

function array_sort_unique($arr){
    sort($arr);
    $prev = null;
    foreach($arr as $key => $item){
        if($item === $prev){
            unset($arr[$key]);
        }
        $prev = $item;
    }
    return array_values($arr);
}

function check_by_replace($number, $digits){
    $result1 = preg_replace("/[$number]/", "", implode($digits));
    $res1 = (empty($result1)) ? "&sub;" : "&nsub;";
    $result2 = str_replace($digits, "",  $number);
    $res2 = (empty($result2)) ? "&sub;" : "&nsub;";
    return[$res1, $res2];
}

function check_by_arrays($number, $digits){
    $arr_dig = array_sort_unique($digits);
    $str_num = (string)$number;
    $format = str_repeat("%1d", count($str_num));
    $arr_num = array_sort_unique(sscanf($str_num, $format));
    $res1 = "&sub;";
    $res2 = "&sub;";
    if($arr_dig !== $arr_num){
        $key_num = 0;
        $key_dig = 0;
        while(($key_num < count($arr_num)) && ($key_dig < count($arr_dig))){
            if($arr_num[$key_num] > $arr_dig[$key_dig]){
                $res1 = "&nsub;";
                $key_dig++;
            }elseif($arr_num[$key_num] < $arr_dig[$key_dig]){
                $res2 = "&nsub;";
                $key_num++;
            }else{
                $key_dig++;
                $key_num++;
            }   
        }   
    }
    return[$res1, $res2];
};

function comparison($number, $digits, $pr = 0){
    $replace_res = check_by_replace($number, $digits);
    $arrays_res = check_by_arrays($number, $digits);
    if($pr > 0){
        print_digits("<br><br>* check_by_replace: *", $digits);
        print_digits(" $replace_res[0] $number,&emsp;$number $replace_res[1]", $digits);
        print_digits("<br>* check_by_array: *", $digits);
        print_digits(" $arrays_res[0] $number,&emsp;$number $arrays_res[1]", $digits);
    }
}   
print"ПРОВЕРКА";

comparison(13579, [1, 9, 5], PR);
comparison(13579, [1, 9, 5, 2], PR);
comparison(13579, [9, 1, 7, 5, 3, 2], PR);
comparison(13579, [1, 9, 5, 9, 1], PR);
comparison(13579391, [1, 9, 5, 3, 2, 7], PR);

printf("<br><br>ТЕСТ БЫСТРОДЕЙСТВИЯ<br>%d сравнений по %d цифр<br>", (int)N, (int)M);

$test_dig = [];
$test_num = [];
for($i = 0; $i < N; $i++){
    $dig = [];
    $num = [];
    for($j = 0; $j < M; $j++){
        $dig[] = mt_rand(0,9);
        $num[] = mt_rand(0,9);
    }
    $test_dig[] = $dig;
    $test_num[] = implode($num);
}

$time0 = microtime(true);
for($i = 0; $i < N; $i++){
    check_by_replace($test_num[$i], $test_dig[$i]);
}
$time1 = microtime(true);
for($i = 0; $i < N; $i++){
    check_by_arrays($test_num[$i], $test_dig[$i]);
}
$time2 = microtime(true);

printf("<br>check_by_replace: %.03f c", $time1 - $time0);
printf("<br>check_by_arrays: %.03f" c, $time2 - $time1);

Результаты:

ПРОВЕРКА

* check_by_replace: * [ 1 9 5 ] ⊂ 13579, 13579 ⊄ [ 1 9 5 ]
* check_by_array: * [ 1 9 5 ] ⊂ 13579, 13579 ⊂ [ 1 9 5 ]

* check_by_replace: * [ 1 9 5 2 ] ⊄ 13579, 13579 ⊄ [ 1 9 5 2 ]
* check_by_array: * [ 1 9 5 2 ] ⊂ 13579, 13579 ⊂ [ 1 9 5 2 ]

* check_by_replace: * [ 9 1 7 5 3 2 ] ⊄ 13579, 13579 ⊂ [ 9 1 7 5 3 2 ]
* check_by_array: * [ 9 1 7 5 3 2 ] ⊂ 13579, 13579 ⊂ [ 9 1 7 5 3 2 ]

* check_by_replace: * [ 1 9 5 9 1 ] ⊂ 13579, 13579 ⊄ [ 1 9 5 9 1 ]
* check_by_array: * [ 1 9 5 9 1 ] ⊂ 13579, 13579 ⊂ [ 1 9 5 9 1 ]

* check_by_replace: * [ 1 9 5 3 2 7 ] ⊄ 13579391, 13579391 ⊂ [ 1 9 5 3 2 7 ]
* check_by_array: * [ 1 9 5 3 2 7 ] ⊂ 13579391, 13579391 ⊂ [ 1 9 5 3 2 7 ]

ТЕСТ БЫСТРОДЕЙСТВИЯ
100000 сравнений по 11 цифр

check_by_replace: 3.922 с
check_by_arrays: 10.482 с

0

Если бы это был C++, я бы сделал так:

bool total(const char * s)
{
    unsigned short int flag = 0;
    unsigned short int mask[] = { 0x0001, 0x0002, 0x0004, 0x0008,
                                  0x0010, 0x0020, 0x0040, 0x0080,
                                  0x0100, 0x0200 };
    for(;*s;++s)
    {
        if ((flag |= mask[*s - '0']) == 0x03FF ) return true;
    }
    return false;
}

Здесь, правда, я не проверяю, что все символы именно цифры. Но смысл - выставляю битовый флаг, если в какой-то момент все цифры выставлены - ура, есть. Само собой, O(n). Меньше быть не может в принципе...

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.