Compare two integer arrays with same length_问答_开发者

[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开发者_JAVA百科 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.

(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(N^k) with a finite k.)

You can try a probabilistic approach - convert the arrays into a number in some huge base B and mod by some prime P, for example sum B^a_i for all i mod some big-ish P. If they both come out to the same number, try again for as many primes as you want. If it's false at any attempts, then they are not correct. If they pass enough challenges, then they are equal, with high probability.

There's a trivial proof for B > N, P > biggest number. So there must be a challenge that cannot be met. This is actually the deterministic approach, though the complexity analysis might be more difficult, depending on how people view the complexity in terms of the size of the input (as opposed to just the number of elements).

I claim that: Unless the range of input is specified, then it is IMPOSSIBLE to solve in onstant extra space, and O(n) running time.

I will be happy to be proven wrong, so that I can learn something new.

Insert all elements from the first array into a hashtable
Try to insert all elements from the second array into the same hashtable - for each insert to element should already be there

Ok, this is not with constant extra space, but the best I could come up at the moment:-). Are there any other constraints imposed on the question, like for example to biggest integer that may be included in the array?

A few answers are basically correct, even though they don't look like it. The hash table approach (for one example) has an upper limit based on the range of the type involved rather than the number of elements in the arrays. At least by by most definitions, that makes the (upper limit on) the space a constant, although the constant may be quite large.

In theory, you could change that from an upper limit to a true constant amount of space. Just for example, if you were working in C or C++, and it was an array of char, you could use something like:

size_t counts[UCHAR_MAX];

Since UCHAR_MAX is a constant, the amount of space used by the array is also a constant.

Edit: I'd note for the record that a bound on the ranges/sizes of items involved is implicit in nearly all descriptions of algorithmic complexity. Just for example, we all "know" that Quicksort is an O(N log N) algorithm. That's only true, however, if we assume that comparing and swapping the items being sorted takes constant time, which can only be true if we bound the range. If the range of items involved is large enough that we can no longer treat a comparison or a swap as taking constant time, then its complexity would become something like O(N log N log R), were R is the range, so log R approximates the number of bits necessary to represent an item.

Is this a trick question? If the authors assumed integers to be within a given range (2^32 etc.) then "extra constant space" might simply be an array of size 2^32 in which you count the occurrences in both lists.

If the integers are unranged, it cannot be done.

You could add each element into a hashmap<Integer, Integer>, with the following rules: Array A is the adder, array B is the remover. When inserting from Array A, if the key does not exist, insert it with a value of 1. If the key exists, increment the value (keep a count). When removing, if the key exists and is greater than 1, reduce it by 1. If the key exists and is 1, remove the element.

Run through array A followed by array B using the rules above. If at any time during the removal phase array B does not find an element, you can immediately return false. If after both the adder and remover are finished the hashmap is empty, the arrays are equivalent.

Edit: The size of the hashtable will be equal to the number of distinct values in the array does this fit the definition of constant space?

I imagine the solution will require some sort of transformation that is both associative and commutative and guarantees a unique result for a unique set of inputs. However I'm not sure if that even exists.

public static boolean match(int[] array1, int[] array2) {

        int x, y = 0;

        for(x = 0; x < array1.length; x++) {
                y = x;
                while(array1[x] != array2[y]) {
                        if (y + 1 == array1.length)
                                return false;
                        y++;
                }
                int swap = array2[x];
                array2[x] = array2[y];
                array2[y] = swap;
        }

        return true;
}

For each array, Use Counting sort technique to build the count of number of elements less than or equal to a particular element . Then compare the two built auxillary arrays at every index, if they r equal arrays r equal else they r not . COunting sort requires O(n) and array comparison at every index is again O(n) so totally its O(n) and the space required is equal to the size of two arrays . Here is a link to counting sort http://en.wikipedia.org/wiki/Counting_sort.

given int are in the range -n..+n a simple way to check for equity may be the following (pseudo code):

// a & b are the array
accumulator = 0
arraysize = size(a)
for(i=0 ; i < arraysize; ++i) {
  accumulator = accumulator + a[i] - b[i]
  if abs(accumulator) > ((arraysize - i) * n) { return FALSE }
}
return (accumulator == 0)

accumulator must be able to store integer with range = +- arraysize * n

How 'bout this - XOR all the numbers in both the arrays. If the result is 0, you got a match.