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

Question

Я хочу код Java, который можно сравнивать следующим образом (например):

<1 2 3 4>  = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>

Я не могу использовать таблицу hashmap или что-то еще; просто чистый код без библиотеки.

Я знаю, что есть два пути.

1. отсортируйте их и сравните индекс массива по индексу

2. используйте два для цикла и сравните внешний индекс с внутренним индексом. Я пытался с этим, но все еще не работает:

   for(int i = 0; i < n; i++)
   {
       for(int j = 0; j < n; j++)
       {   
           if(a[i] != a[j] && j == n)
               return false;
       }
   }
   return true;
   

что-то не так с кодом? спасибо

Answer 1

Сортировка и сравнение. Вы не можете получить сложность лучше, чем это, и любое «улучшение», которое вы делаете в скорости, рискует, что ваш код будет неправильным.

[править] На самом деле .... если вы знаете ваши числа относительно малы (например, скажем: массивы содержат только числа от 0 до 1000), то есть альтернатива в O (n). Примерно так (извините, если синтаксис неправильный, я в последнее время не пользовался java):

int count[1001]; // already intialized to 0

for(int i=0;i<n;i++){ count[a[i]]++; count[b[i]]--;}
bool arrays_identical = true;
for(int i=0;i<=1000 && arrays_identical; i++)
    arrays_identical &= count[i]==0;

Отказ от ответственности: этот код не содержит «проверок работоспособности» (т. Е. Массивы действительно имеют длину «n», числа в заданном интервале) - это только для иллюстрации принципа.

Answer 2

Arrays.sort(a);
Arrays.sort(b);
return Arrays.equals(a, b);

Answer 3

Так как это домашнее задание, я собираюсь предположить, что простое квадратичное решение (которое является вашей первоначальной попыткой) вполне подходит В этом случае вы можете сделать что-то вроде этого:

int count(int[] nums, int x) {
    int count = 0;
    for (int num : nums) {
        if (num == x) count++;
    }
    return count;
}   
boolean equals(int[] arr1, int[] arr2) {
    if (arr1.length != arr2.length) return false;
    for (int x : arr1) {
        if (count(arr1, x) != count(arr2, x)) return false;
    }
    return true;
}

Это жертвует скоростью для ясности: это очевидно правильно !!

Советы

• Используйте для каждого, когда это применимо; это всегда читается для лучшей читаемости
• Вспомогательные функции улучшают читабельность и возможность повторного использования!

Answer 4

Это проблема O (n ^ 2). Никакое другое решение не является более быстрым, чем прямое сравнение двух массивов.

Решение Virgil - это круто, за исключением того факта, что это не совсем O (n) производительность. Это действительно O (n + 1000) производительность. Сравнение массивов во второй раз для установки логической переменной является дорогостоящим и имеет неприятные последствия в небольших массивах.

Решение, которое вы написали, является лучшим, за исключением ошибок.

Вот исправленная ошибка версии.

boolean[] matchedPositions = new boolean[n];
for(int k = 0; k < n; k++
{
    matchedPositions[k] = false;
}

for(int i = 0; i < n; i++)
{
    for(int j = 0; j < n; j++)
    {   
        if(matchedPositions[j] == false && a[i] == a[j])
        {
             matchedPositions[j] = true;
             break;
        }

        if(j == n - 1)
        {
            return false;
        }
    }
}
return true;

В этом случае, если в случае совпадения целого числа, внутренний цикл будет разорван и установлен или помечено совпадающее положение. Это требуется для массивов с повторяющихся записей , это позволит избежать совпадения двух записей в левом массиве с одной записью в правом массиве.

Если в случае, если совпадение не произошло, что идентифицируется как j == n - 1 , вы вернете false.

Поскольку мы ожидаем, что значение по умолчанию false в логическом значении, лучше пометить initialize it.

На самом деле это решение имеет O (n log n + n) снижение производительности. Сортировка и сравнение также приводят к снижению производительности O (n ^ 2 + n). Сортировка имеет производительность O (n ^ 2) и один цикл для проверки. Но сортировка изменяет содержимое массива, а это не так.

Answer 5

Прежде чем вы действительно запустите более сложное в вычислительном отношении решение, вы можете запустить быстрый тест O (n), чтобы проверить, совпадают ли массивы. Бывают случаи, когда это приводит к ложному положительному результату, и вы можете использовать более интенсивные вычислительные средства для дальнейшего исследования. Если он возвращает false, вы можете быть уверены, что массивы разные.

Основной подход состоит в том, чтобы сделать кумулятивное XOR между i-м элементом двух массивов. Если полученный XOR не равен нулю, то вы знаете, что эти два массива различны. Если XOR равно нулю, они могут быть одинаковыми, но для подтверждения требуется больше работы.

int c_xor = 0;  // XOR accumulator

for (int i = 0; i < n; ++i)
    c_xor ^= arr1[i] ^ arr2[i];

// They're different if c_xor != 0; the might be the same if c_xor == 0
return c_xor == 0;

Answer 6

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

{1, 2, 3} считается равным {4, 3, 2, 1}

Answer 7

если вы возьмете один массив за 1,2,3,4,3,1,2,4, то решение будет таким.

2n = общее количество целых чисел: 8

//program
int i, j, n = 4;
for(i = 0; i < n; i++)
  for(j = n; j < 2n; j++)
   {
     if( a[i] != a[j])
      { 
        j++;
      }
     else
     {
       i++; exit();
     }
  }  

if (i == n) 
{ //They both are equal;
}
else if(i != n)
{
//They both are not equal;
}

Если это не работает, пожалуйста, прокомментируйте это. Спасибо.

Answer 8

Вот исправление для кода, который вы опубликовали.

for(int i = 0; i < n; i++)
{
    int j;
    for(j = 0; j < n; j++)
    {   
        if(a[i] == b[j]) break;
    }
    if (j == n) return false;
}
return true;

Однако этот алгоритм будет нарушен для массивов, содержащих дубликаты. Например, массив {1, 1, 2, 3} будет найден как совпадение с массивом {1, 2, 2, 3}.

Я бы настоятельно рекомендовал вместо этого реализовать алгоритм сортировки и сравнения.