Question: Given two arrays, determine whether one is a permutation of the other.
By the definition, if two array contain the same elements regardless of the order, they are in the same permutation group. For example, [2 3 1 1 4] and [1 1 3 4 2] are permutations of each other. But [2 3 1 1 4] and [1 2 3 4 2] are not.
Solution 1:
Sort each array, and compare each element from the beginning to the end.
The sorting costs O(nlogn). The comparison costs O(n). No additional space is needed if we can change the original array.
Solution 2:
Use the hash map to record how many times each element occurs in each array. For example, from [2 3 1 1 4], we generate the hash map:
<2, 1> <3, 1> <1, 2> <4, 1>
Similarly, we build the hash map for the other array and compare two hash maps.
The time complexity is O(n). O(n) additional space is needed.
Solution 3:
Is there an O(n) time and constant space algorithm? We have an approximate algorithm using the min-hash (http://en.wikipedia.org/wiki/MinHash)
We define a set of hash functions. For example, the hash function h_1 hashes an integer x to another integer h_1(x).
When using a hash function, we get two arrays of the hashed values, and from each array we use the minimum element to represent the array. The property of the min-hash says that the probability that two minimum elements are the same is equal to the jaccard distance between two arrays.
We can use k hash functions to get k values for each array. The combination of k values can be viewed as a signature of the array. If all of the k values are the same, we can assume two arrays are permutations of each other.
By the definition, if two array contain the same elements regardless of the order, they are in the same permutation group. For example, [2 3 1 1 4] and [1 1 3 4 2] are permutations of each other. But [2 3 1 1 4] and [1 2 3 4 2] are not.
Solution 1:
Sort each array, and compare each element from the beginning to the end.
The sorting costs O(nlogn). The comparison costs O(n). No additional space is needed if we can change the original array.
Solution 2:
Use the hash map to record how many times each element occurs in each array. For example, from [2 3 1 1 4], we generate the hash map:
<2, 1> <3, 1> <1, 2> <4, 1>
Similarly, we build the hash map for the other array and compare two hash maps.
The time complexity is O(n). O(n) additional space is needed.
Solution 3:
Is there an O(n) time and constant space algorithm? We have an approximate algorithm using the min-hash (http://en.wikipedia.org/wiki/MinHash)
We define a set of hash functions. For example, the hash function h_1 hashes an integer x to another integer h_1(x).
When using a hash function, we get two arrays of the hashed values, and from each array we use the minimum element to represent the array. The property of the min-hash says that the probability that two minimum elements are the same is equal to the jaccard distance between two arrays.
We can use k hash functions to get k values for each array. The combination of k values can be viewed as a signature of the array. If all of the k values are the same, we can assume two arrays are permutations of each other.
| Hot Deals | ||
|
No comments:
Post a Comment