Найти максимальное вхождение цифры k в заданном списке натуральных чисел

Question

Например: k = 2, arr [] = 13,12,242,32,1532,1222, 33 Выход: 3 (1222 имеет наибольшее 2 с, что равно 3). Как решить со временем сложность лучше, чем O (n²)т.е. две петли

Answer 1

Ну, чтобы решить эту проблему, мы должны проверить все цифры каждого числа в списке.

Итак, предположим, что числа имеют Maximum_length = m, и у нас есть всего n чисел. Тогда мы можем достичь сложности O (n * m). Вот пример кода C ++, и здесь я предполагаю, что все числа в списке помещаются в 32-разрядное целое число со знаком. Он также дает правильный ответ для предоставленного вами контрольного примера.

#include <vector>
#include <iostream>

int calculate_ans( int number, int k ) {

    if( number == 0 ) {
        if( k == 0 ) return 1;
        return 0;
    }

    if( number < 0 ) number = -number;

    int ans = 0;

    while( number > 0 ) {
        int last_digit = ( number % 10 );
        if( last_digit == k ) ans++;
        number /= 10;
    }

    return ans;

}


int solve( const std::vector<int>& number_list, int k ) {
    int best = 0;
    for( const auto& number : number_list ) best = std::max( best, calculate_ans( number, k ) );
    return best;
}

int main() {
    std::vector< int > arr = { 13, 12, 242, 32, 1532, 1222, 33};
    std::cout << solve( arr, 2 ) << std::endl;
}