Алгоритм проверки наличия одинаковых элементов в двух несортированных целочисленных массивах?

Я все еще новичок, когда дело доходит до программирования на C, поэтому, пожалуйста, будьте внимательны в объяснениях. Кроме того, это домашнее задание, поэтому я был бы признателен, если бы вы помогли мне решить эту проблему. Я просмотрел сайт и смог найти только сообщения, похожие на этот вопрос. В тех, которые я нашел, упоминались такие вещи, как хэш-таблицы, которые я не изучал, поэтому я сомневаюсь, что такие вещи можно использовать.

Для моего задания у меня есть два несортированных целочисленных массива одинаковой длины. Они могут иметь только целые числа в диапазоне 0-99. Допускаются повторяющиеся элементы. Цель состоит в том, чтобы увидеть, имеют ли они одинаковые элементы, поэтому проверьте, равны ли они, не сортируя их. Мой профессор также сказал, что он должен выполняться в линейном времени, поэтому их сортировка невозможна.

Например,

A[4]={1,2,3,4}
B[4]={4,3,2,1}

Эти массивы будут равны. Однако,

A[3]={1,1,2}
B[3]={2,2,1}

Эти массивы не равны.

Алгоритм, который я придумал, выглядит следующим образом:
Первый цикл for выполняет итерацию по первому массиву, а внутренний цикл for выполняет итерацию по второму массиву. Он будет проверять, равен ли текущий элемент в первом массиве элементу во втором. Если они равны, то внешний цикл повторяется, а внутренний цикл for снова начинается с первого элемента, проверяя, совпадает ли когда-либо текущий элемент в первом массиве с элементом во втором. Если нет, то он выходит из обоих циклов и возвращает 0, указывающий, что они не равны. Этот алгоритм не работает за линейное время. Кроме того, он не проверяет наличие дубликатов, поскольку внутренний цикл for каждый раз проверяет все элементы во втором массиве.

Я думал об изменении значения элемента во втором массиве на что-то чрезвычайно большое каждый раз, когда обнаруживалось, что оно равно элементу в первом массиве. Я думаю, что таким образом это избавит от проблемы дублирования. Но мне все еще нужна помощь в создании более быстрого алгоритма и понимании моей ошибки. Спасибо.


c arrays multiset
person Cactus    schedule 11.10.2015    source источник
comment
Я думаю, вы хотите использовать гистограмму там.   -  person melpomene    schedule 11.10.2015

Ответы (3)


arrow_upward
3
arrow_downward

Просто переосмыслите свою задачу: вам нужно выяснить, является ли один массив перестановкой другого. Чтобы решить эту проблему, вам нужно только проверить, сколько нулей, единиц, ..., 99 в каждом массиве. То есть,

  • пусть новый массив int count[100] будет инициализирован всеми нулями
  • для каждого i: увеличить count[a[i]] и уменьшить count[b[i]]
  • если count[] состоит из всех нулей, то a[] и b[] являются перестановками.
person Matt    schedule 11.10.2015
comment
Если после этого вы выполняете декремент в отдельном цикле, вам не нужно проверять count для всех нулей. - person melpomene; 11.10.2015
comment
@melpomene Почему? (Конечно, inc/dec должны идти в том же цикле, но я не вижу способа избежать дополнительной проверки в любом случае). - person Matt; 11.10.2015
comment
@melpomene Я уверен, что вы, вероятно, правы, но у меня проблемы с тем, чтобы понять, как, мой мозг с дефицитом кофеина. Не хотите расширяться? Я предполагаю, что есть способ выйти раньше, если во время цикла декремента выполняется определенное условие. - person underscore_d; 11.10.2015
comment
@underscore_d: зациклиться на a[] увеличении счетчиков, затем зациклиться на b[] уменьшении счетчиков. Если какой-либо счетчик станет отрицательным во втором цикле, выйдите раньше. - person Blastfurnace; 11.10.2015
comment
@Blastfurnace Проверка потенциального отрицательного счетчика декремента должна быть выполнена N раз. Проверка счетчика равна 0, после чего выполняется 100 раз. С большими массивами лучше пройти проверку позже. - person chux - Reinstate Monica; 12.10.2015

arrow_upward
1
arrow_downward

A good and simple trick to sort that out is :

  • сортировать массив A (в (O(n log n))
  • сортировать массив B (в O(n log n))
  • сравнить оба массива (за O(n))

    • результат в целом O (n log n)

    person Matthieu C    schedule 27.05.2016

    arrow_upward
    0
    arrow_downward

    Три вещи, на которые следует обратить внимание: сумма элементов массива 1 и массива 2, умножение
    элементов массива 1 и массива 2 и их нулевой счет. Если все удовлетворено, то они равны. #включать

    int main(void)
{
    int A[4] = { 4 , 3 , 2 , 1 }; 

    int B[4] = { 6 , 2 , 1 , 1 };

    int varA = 1 , varB = 1;

    int sumA = 0 , sumB = 0;

    int zeroCountA = 0 , zeroCountB = 0; 

    for( int n = 0 ; n < 4 ; n++ )
    {
        if( A[n] != 0)
        {
            varA *= A[n];
            sumA += A[n];
        }
        else
        {
            zeroCountA++;
        }
    }

    for( int n = 0 ; n < 4 ; n++ )
    {
        if( B[n] != 0)
        {
            varB *= B[n];
            sumB += B[n];
        }
        else
        {
            zeroCountB++;
        }
    }

    if( sumA == sumB )
    {
        if( varA == varB )
        {
            if( zeroCountA == zeroCountB )
                printf("A = B\n");
        }
        else
        {
            printf("A != B\n");
        }
    }
    else
    {
        printf("A != B\n");
    }
}
    person machine_1    schedule 11.10.2015
    comment
    Этот подход в общем случае не работает: Пример счетчика: { 2,8, 2,3} { 4,4, 1,6 } --> и сумма 15, и произведение 96. Этот алгоритм сообщает, что массивы равны, когда это не так. - person chux - Reinstate Monica; 12.10.2015
    comment
    да, этот встречный пример говорит сам за себя. - person machine_1; 12.10.2015