Let's say I have an array of ints: [1, 2, 4, 9, 5, 6, 8, 7]. I have a second array, [8, 7, 6]. What I want to know is, does the first array end with the same values as the second array, not necessarily in the same order? (In this case, the result should be true.)

Invariants that can be relied upon:

• array1.Length > array2.Length
• All elements in array1 are unique.
• All elements in array2 are unique.

What is the simplest way to answer this question? It would be particularly nice if there was a reasonably efficient solution that does not require any allocations.

CodePudding user response：

You can have a simple O(nlogn) complexity (n = size of array2) in this way:

• sort array2
• sort the last n elements of array1
• compare element-by-element array2 and the last n element of array1

This should be the best you can do without any additional allocation

CodePudding user response：

I think LINQ is the easiest way to do this:

using System.Linq;

bool EndsWithSubset(int[] array1, int[] array2)
{
    return array1
        .TakeLast(array2.Length)
        .ToHashSet()
        .SetEquals(array2);
}

Example usage:

Console.WriteLine(
    EndsWithSubset(
        new [] { 1, 2, 4, 9, 5, 6, 8, 7 },
        new [] { 8, 7, 6 }
    ));   // True

CodePudding user response：

You can query the arrays with a help of Linq. Here we exploit the fact that all values are unique (no duplicates):

 bool contains = !array1
                    .Skip(array1.Length - array2.Length)
                    .Except(array2)
                    .Any();

Here we

1. Obtain array1 suffix with a help of .Skip(array.Length - array2.Length)
2. Subtract array2 with .Except(array2)
3. Then check if any items remain - .Any()

CodePudding user response：

If the 2nd array is usually not that long you just might sort both sequences and compare element wise. If it is long the cost for sorting is probably high and using a hashset would turn out more effective.

 bool endsEqual = arr1.TakeLast(arr2.Length)
                      .OrderBy(i => i)
                      .SequenceEqual(arr2.OrderBy(i => i));

CodePudding user response：

Try this. Maybe the code looks bulky for somebody, but IMHO it is going to be the fastest one, since it doesn't need to be translated from Linq.

var arr1 = new int[] { 1, 2, 4, 9, 5, 6, 8, 7};
var arr2 = new int[]  { 8, 7, 6};

var startIndex = arr1.Length - arr2.Length;
for (var i = 0; i < arr2.Length; i  ) {
    for (var j = startIndex; j < arr1.Length; j  ) {
        if (arr1[j] == arr2[i]) { arr1[j] = -1; break; }
    }
}

var isContaining = true;
for (var j = startIndex; j < arr1.Length; j  ) {
    if (arr1[j] != -1) { isContaining = false; break; }
}

CodePudding user response：

Most efficient solution would be to XOR all the elements of arr1 ( last arr2.Length elements) and arr2.

As the items in both the arrays are unique. And if we XOR both arrays it will produce 0 if both arrays same items.

It will run in O(n)

bool areEqual(int arr1[], int arr2[])
{
    int x = arr1[0];
    int y = arr2[0];

    for (int i = 1; i < arr1.Length; i  ) {
        x ^= arr1[i];
    }
 
    for (int i = 1; i < arr2.Length; i  ) {
        y ^= arr2[i];
    }

    int xor = x ^ y;

    if (xor == 0)
        return true;

    return false;
}

Sorry if there’s is any typo error. As I have typed from phone.