#массивы #алгоритм
Дан массив цифр (любой длины) и число.
Как проверить, что число содержит все цифры из массива?
Был вариант решать эту задачу путем деления числа на цифры с последующей проверкой,
но этот вариант слишком громоздкий.
Можете предложить более быстрый способ ?
Ответы
Ответ 1
Создаем массив из 10 элементов, равных нулю. Назовем его CNT. Заведем числовую переменную K=1 Бежим по входному массиву, увеличиваем CNT[цифра] на 1. Умножаем K на 10. Закончили читать цифры. Делим K на 10 (т.к. один лишний раз умножили) Убеждаемся, что K<=ЧИСЛО и K*10>ЧИСЛО(что бы лишней работы не делать). Т.е. проверяем, что число содержит столько же разрядов, сколько цифр в массиве. В цикле делим ЧИСЛО на 10, вычитаем 1 из CNT[остаток-от-деления]. Если элемент в CNT стал меньше 0 - число не совпадает с массивом. Так как мы знаем, что разрядность ЧИСЛА была равна длине массива и ни один из элементов CNT не стал отрицательным - значит все цифры были в нужном количестве ! Итого для работы нам надо один раз пройти по входному массиву и один раз по разрядам числа. Т.е. сложность порядка O(2n). В отличие от поиска каждой отдельной цифры перебором массива (даже если это встроенная функция), где сложность O(n*n)Ответ 2
Можно перевести число и цифры в строку/символы. И выполнить нужное количество раз поиск по строке.Ответ 3
Можно выделить каждый разряд (видимо, десятичный - остаток от деления на 10) и проверить, входят ли получившиеся цифры в заданный массив.Ответ 4
Смотрите. Вам нужно по сути проверить вхождение одного множества в другое. Вы не указали конкретный язык, но во многих языках (или их стандартных библиотеках) есть понятие множества и операции над ним. Теперь, ваш массив цифр нужно превратить в множество (например, завести пустое множество и добавлять цифры по одной). Набор цифр числа проще всего получить, переведя число в строковое представление и отбросив возможные «лишние» символы (например, минус). Строек можно легко разобрать на символы и упаковать во множество. После получения двух множеств вопрос становится тривиальным: операция проверки вхождения обычно вам дана языком.Ответ 5
Пример на 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Ответ 6
Алгоритм может быть такой: 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]);Ответ 7
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)) ? "⊂" : "⊄"; $result2 = str_replace($digits, "", $number); $res2 = (empty($result2)) ? "⊂" : "⊄"; 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 = "⊂"; $res2 = "⊂"; 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 = "⊄"; $key_dig++; }elseif($arr_num[$key_num] < $arr_dig[$key_dig]){ $res2 = "⊄"; $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("
* check_by_replace: *", $digits); print_digits(" $replace_res[0] $number, $number $replace_res[1]", $digits); print_digits("
* check_by_array: *", $digits); print_digits(" $arrays_res[0] $number, $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("
ТЕСТ БЫСТРОДЕЙСТВИЯ
%d сравнений по %d цифр
", (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("
check_by_replace: %.03f c", $time1 - $time0); printf("
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 сОтвет 8
Если бы это был 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). Меньше быть не может в принципе...
Комментариев нет:
Отправить комментарий