Проверьте, являются ли два массива перестановками друг друга
Учитывая два несортированных массива одинакового размера, напишите функцию, которая возвращает истину, если два массива являются перестановками друг друга, в противном случае - ложь.
Примеры:
Ввод: 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)
Лучшее решение - использовать хеширование.
- Создайте карту хеша для всех элементов arr1 [], чтобы элементы массива были ключами, а их счетчики - значениями.
- Пройдите по arr2 [] и найдите каждый элемент arr2 [] на карте хешей. Если элемент найден, уменьшите его счетчик в хеш-карте. Если не найден, вернуть false.
- Если все элементы найдены, верните 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> |
Arrays are permutations of each other
Временная сложность этого метода составляет O (n) при предположении, что у нас есть хэш-функция, которая вставляет и находит элементы за время O (1).
Эта статья предоставлена Рави . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше
Вниманию читателя! Не прекращайте учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .