Way to judge if two Arrays are identical?

By identical I mean two Arrays contain same elements, order of elements in Arrays are not matter here.

The solution I came up with is like this(which turns out a wrong approach as pointed out in comments):

 if the size of two Arrays are equal
 See True, find all elements of Array A in Array B
 All Found,  find all eleme开发者_开发问答nts of Array B in Array A
 All Found, then I get conclusion two Arrays are identical

However, is there better algorithm in term of time complexity?

Let's say you have an User[] array 1 and User[] array 2. You can lop through array one and add them to Dictionary<User, int> dictionary where the key is the user and the value is a count. Then you loop through the second array and for each user in array 2 decrement the count in the dictionary (if count is greater than 1) or remove the element (if count is 1). If the user isn't in the dictionary, then you can stop, the arrays don't match.

If you get to the end and had previously checked length of the arrays is same, then the arrays match. If you hadn't checked length earlier (which of course you still should have), then you can just verify the dictionary is now empty after completely looping through array 2.

I don't know exactly what the performance of this is, but it will be faster than sorting both lists and looping through them comparing element by element. Takes more memory though, but if the arrays are not super large then memory usage shouldn't be an issue.

First, check the size of the two arrays. If they aren't equal then they don't contain the same elements.

After that, sort both the arrays in O(n lg(n)). Now, just check both the arrays element-by-element in O(n). As they are sorted, if they are equal then they will be equal in every position.

Your approach doesn't work, as it would treat [0, 1, 1] as being equal to [0, 0, 1]. Every item in A is in B and vice versa. You'd need to count the number of occurrences of each item in A and B. (You then don't need to do both, of course, if you've already checked the lengths.)

If the contents are sortable, you can sort both and then compare element-by-element, of course. That only works if you can provide a total ordering to elements though.

Sort both arrays according to a strict ordering and compare them term-by-term.

Update: Summarizing some of the points that have been raised, here the efficiency you can generally expect:

• strict ordering available: O(log N) for sorting plus comparing term-by-term
• equality and hash function available: compare hash counts term-by-term, plus actual object comparisons in the event of hash collisions.
• only equality, no hashing available: must count each element or copy one container and remove (efficiency depends on the container).

The complexity of comparison term-by-term is linear in the position of the first mismatch.

My idea is to loop through the first array and look for items in the second array. The only issue of course is that you can't use an item in the second array twice. So, make a third array of booleans. This array indicates which items in array 2 'have been used'.

Loop through the first array. Inside that loop through each element in the second array to see if you can 'find' that element in the second array, but also check the third array to verify that the position in the second array hasn't been used. If you find a match update that position in the third array and move on.

You should only need to do this once. If you finish and you found a match for all items in array 2 then no unmatched items remain in array 2. You don't need to then loop through array 2 and see if array 1 contains the item.

Of course before you start all that check that the lengths are the same.

If you don't mind extra space you can do some like HashMap to Store the (element,count) pairs of the first array then check if the second array matches up; this would be linear in N (size of biggest array)

If the array sizes are identical and all of the elements in Array A are in Array B, then there is no need to verify that all of the elements in array B are in Array A. So at the very least you can omit that step.

EDIT: Depends on the definition of the problem. This solution would work if and only if his original solution would work, which it wouldn't if the arrays can have duplicate items and you weren't counting or marking them as "used."