Проверьте, являются ли два массива перестановками друг друга

Опубликовано: 21 Января, 2022

Учитывая два несортированных массива одинакового размера, напишите функцию, которая возвращает истину, если два массива являются перестановками друг друга, в противном случае - ложь.

Примеры:

 Ввод: arr1 [] = {2, 1, 3, 5, 4, 3, 2}
       arr2 [] = {3, 2, 2, 4, 5, 3, 1}
Выход: Да

Ввод: arr1 [] = {2, 1, 3, 5,}
       arr2 [] = {3, 2, 2, 4}
Выход: Нет

Мы настоятельно рекомендуем вам свернуть браузер и сначала попробовать это самостоятельно.
Простое решение - отсортировать оба массива и сравнить отсортированные массивы. Временная сложность этого решения O (nLogn)
Лучшее решение - использовать хеширование.

  1. Создайте карту хеша для всех элементов arr1 [], чтобы элементы массива были ключами, а их счетчики - значениями.
  2. Пройдите по arr2 [] и найдите каждый элемент arr2 [] на карте хешей. Если элемент найден, уменьшите его счетчик в хеш-карте. Если не найден, вернуть false.
  3. Если все элементы найдены, верните true.

Below is the implementation of this approach.  

C++

// A C++ program to find one array is permutation of other array
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if arr1[] and arr2[] are permutations of each other
bool arePermutations(int arr1[], int arr2[], int n, int m)
{
     
    // Arrays cannot be permutations of one another unless they are
    // of the same length
    if(n != m)
    {
        return false;
    }
   
    // Creates an empty hashMap hM
    map<int, int> hm;
     
    // Traverse through the first array and add elements to hash map
    for (int i = 0; i < n; i++)
    {
        int x = arr1[i];
        hm[x]++;
    }
     
    // Traverse through second array and check if every element is
    // present in hash map
    for (int i = 0; i < m; i++)
    {
        int x = arr2[i];
       
        // If element is not present in hash map or element
        // is not present less number of times
        if(hm[x] == 0)
        {
            return false;
        }
        hm[x]--;
    }
    return true;
}
 
// Driver function to test above function
int main() {
    int arr1[] = {2, 1, 3, 5, 4, 3, 2};
    int arr2[] = {3, 2, 2, 4, 5, 3, 1};
    int n = sizeof(arr1)/sizeof(arr1[0]);
    int m = sizeof(arr2)/sizeof(arr2[0]);
    if (arePermutations(arr1, arr2, n, m))
        cout << "Arrays are permutations of each other" << endl;
    else
        cout << "Arrays are NOT permutations of each other" << endl;
     
    return 0;
}
 
// This code is contributed by avanitrachhadiya2155

Java

// A Java program to find one array is permutation of other array
import java.util.HashMap;
 
class Permutaions
{
    // Returns true if arr1[] and arr2[] are permutations of each other
    static Boolean arePermutations(int arr1[], int arr2[])
    {
        // Arrays cannot be permutations of one another unless they are
        // of the same length
        if (arr1.length != arr2.length)
            return false;
       
        // Creates an empty hashMap hM
        HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
 
        // Traverse through the first array and add elements to hash map
        for (int i = 0; i < arr1.length; i++)
        {
            int x = arr1[i];
            if (hM.get(x) == null)
                hM.put(x, 1);
            else
            {
                int k = hM.get(x);
                hM.put(x, k+1);
            }
        }
 
        // Traverse through second array and check if every element is
        // present in hash map
        for (int i = 0; i < arr2.length; i++)
        {
            int x = arr2[i];
 
            // If element is not present in hash map or element
            // is not present less number of times
            if (hM.get(x) == null || hM.get(x) == 0)
                return false;
 
            int k = hM.get(x);
            hM.put(x, k-1);
        }
        return true;
    }
 
    // Driver function to test above function
    public static void main(String arg[])
    {
        int arr1[] = {2, 1, 3, 5, 4, 3, 2};
        int arr2[] = {3, 2, 2, 4, 5, 3, 1};
        if (arePermutations(arr1, arr2))
            System.out.println("Arrays are permutations of each other");
        else
            System.out.println("Arrays are NOT permutations of each other");
    }
}

Python3

# Python3 program to find one
# array is permutation of other array
from collections import defaultdict
 
# Returns true if arr1[] and
# arr2[] are permutations of
# each other
def arePermutations(arr1, arr2):
    # Arrays cannot be permutations of one another
    # unless they are of the same length
    if (len(arr1) != len(arr2)):
        return False
       
    # Creates an empty hashMap hM
    hM = defaultdict (int)
 
    # Traverse through the first
    # array and add elements to
    # hash map
    for i in range (len(arr1)):
         
        x = arr1[i]
        hM[x] += 1
         
    # Traverse through second array
    # and check if every element is
    # present in hash map
    for i in range (len(arr2)):
        x = arr2[i]
 
        # If element is not present
        # in hash map or element
        # is not present less number
        # of times
        if x not in hM or hM[x] == 0:
             return False
 
        hM[x] -= 1
        
    return True
 
# Driver code
if __name__ == "__main__":
   
    arr1 = [2, 1, 3, 5, 4, 3, 2]
    arr2 = [3, 2, 2, 4, 5, 3, 1]
    if (arePermutations(arr1, arr2)):
        print("Arrays are permutations of each other")
    else:
        print("Arrays are NOT permutations of each other")
         
# This code is contributed by Chitranayal

C#

// C# program to find one array
// is permutation of other array
using System;
using System.Collections.Generic;
 
public class Permutaions {
    // Returns true if arr1[] and arr2[]
    // are permutations of each other
    static Boolean arePermutations(int[] arr1, int[] arr2)
    {
        // Arrays cannot be permutations of one another if
        // they are not the the same length
        if (arr1.Length != arr2.Length)
            return false;
 
        // Creates an empty hashMap hM
        Dictionary<int, int> hM = new Dictionary<int, int>();
 
        // Traverse through the first array
        // and add elements to hash map
        for (int i = 0; i < arr1.Length; i++) {
            int x = arr1[i];
            if (!hM.ContainsKey(x))
                hM.Add(x, 1);
            else {
                int k = hM[x];
                hM.Remove(x);
                hM.Add(x, k + 1);
            }
        }
 
        // Traverse through second array and check if every
        // element is present in hash map (and the same
        // number of times)
        for (int i = 0; i < arr2.Length; i++) {
            int x = arr2[i];
 
            // If element is not present in hash map or
            // element is not present the same number of
            // times
            if (!hM.ContainsKey(x))
                return false; // Not present in the hash map
 
            int k = hM[x];
            if (k == 0)
                return false; // Not present the same number
                              // of times
            hM.Remove(x);
            hM.Add(x, k - 1);
        }
        return true;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr1 = { 2, 1, 3, 5, 4, 3, 2 };
        int[] arr2 = { 3, 2, 2, 4, 5, 3, 1 };
        if (arePermutations(arr1, arr2))
            Console.WriteLine("Arrays are permutations of each other");
        else
            Console.WriteLine("Arrays are NOT permutations of each other");
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
// A Javascript program to find one array
/// is permutation of other array
     
    // Returns true if arr1[] and arr2[]
    // are permutations of each other
    function arePermutations(arr1,arr2)
    {
        // Arrays cannot be permutations of
        // one another unless they are
        // of the same length
        if (arr1.length != arr2.length)
            return false;
        
        // Creates an empty hashMap hM
        let hM = new Map();
  
        // Traverse through the first array
        // and add elements to hash map
        for (let i = 0; i < arr1.length; i++)
        {
            let x = arr1[i];
            if (!hM.has(x))
                hM.set(x, 1);
            else
            {
                let k = hM[x];
                hM.set(x, k+1);
            }
        }
  
        // Traverse through second array and
        // check if every element is
        // present in hash map
        for (let i = 0; i < arr2.length; i++)
        {
            let x = arr2[i];
  
            // If element is not present in
            // hash map or element
            // is not present less number of times
            if (!hM.has(x) || hM[x] == 0)
                return false;
  
            let k = hM[x];
            hM.set(x, k-1);
        }
        return true;
    }
     
    // Driver function to test above function
    let arr1=[2, 1, 3, 5, 4, 3, 2];
    let arr2=[3, 2, 2, 4, 5, 3, 1];
    if (arePermutations(arr1, arr2))
        document.write(
        "Arrays are permutations of each other"
        );
    else
        document.write(
        "Arrays are NOT permutations of each other"
        );
     
    // This code is contributed by rag2127
     
</script>
Output
Arrays are permutations of each other

Временная сложность этого метода составляет O (n) при предположении, что у нас есть хэш-функция, которая вставляет и находит элементы за время O (1).
Эта статья предоставлена Рави . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .