Let's say I have these 3 integer arrays:
int[] a = {1, 2, 3};
int[] b = {3, 4, 5};
int[] c = (2, 1, 3};
I'm looking for the most efficient code that will consider a the same as c (because they contain the same numbers but in a different order), but consider a different from b, and b different from c.
I know I can sort them all so that c becomes {1, 2, 3} and therefore the same as a, but I'm comparing hundreds of arrays with more than three numbers each and I don't want my program to sort each one of them, I'm thinking there must be a better way.
Also, taking the sum, for example, wouldn't work because the sum of numbers in {1, 4, 5} is the same as that of numbers in {1, 3, 6}.
And the product wouldn't work either because the product of numbers in {1, 2, 6} is the same as that of numbers in {1, 3, 4}.
Sorting is an O(nlog(n) operation (in the worst case). You could, instead, have an O(n) solution by running over both arrays and just counting the elements in it:
EDIT:
While it won't change the big-O notation of the algorithm, a slightly less elegant solution could perform better for non-matching arrays by failing fast: