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

Question

Я по-прежнему новичок, когда дело доходит до программирования на языке 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} 

Данные массивы не равны.

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

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

Answer 1

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

• пусть новый массив int count[100] быть инициализирован нулями
• для каждого I: приращение count[a[i]] и уменьшает count[b[i]]
• если count[] состоит из всех нулей, то A [] и B [] являются перестановками.

Answer 2

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

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"); 
    } 
} 

Answer 3

Хороший и простой трюк, чтобы разобраться, что из это:

сортировать массив А. (в (O (п § п))

сортировать массив B (в O (п § п))

сравнить оба массивы (в O (N))

в результате чего все во всем O (п § п)