Menu
[Description] Given two integer arrays with the same length. Design an algorithm which can judge whether they're the same. The definition of "same" is that, if these two arrays were in sorted order, the elements in corresponding position should be the same.
[Example] <1 2 3 4> = <3 1 2 4> <1 2 3 4> != <3 4 1 1> [Limitation] The algorithm should require constant extra space, and O(n) running time.
830
equals(int[] a, int[] a2) method returns true if the two specified arrays of ints are equal to one another. Two arrays are equal if they contain the same elements in the same order. Two array references are considered equal if both are null.
A simple way is to run a loop and compare elements one by one. Java provides a direct method Arrays. equals() to compare two arrays. Actually, there is a list of equals() methods in the Arrays class for different primitive types (int, char, ..etc) and one for Object type (which is the base of all classes in Java).
(Probably too complex for an interview question.)
(You can use O(N) time to check the min, max, sum, sumsq, etc. are equal first.)
Use no-extra-space radix sort to sort the two arrays in-place. O(N) time complexity, O(1) space.
Then compare them using the usual algorithm. O(N) time complexity, O(1) space.
(Provided (max − min) of the arrays is of O(Nk) with a finite k.)
168
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
