Multiple array intersection in javascript

How to write in javascript(w/wth JQuery) to find values that intersect between arrays?

It should be like

var a = [1,2,3]
var b = [2,4,5]
var c = [2,3,6]

and the intersect function should returns array with value {2}. If possible it could applicable for any number of arrays.

Thanks

Answers:

Answer

There are many ways to achieve this.

Since you are using jQuery I will suggest use grep function to filter the value that are present in all three array.

var a = [1, 2, 3]
var b = [2, 4, 5]
var c = [2, 3, 6]

var result = $.grep(a, function(value, index) {
  return b.indexOf(value) > -1 && c.indexOf(value) > -1;
})
console.log(result)
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Explanation: Loop over any array and filter out the values that are present in other array.

Update (for multimidensional array):

Concept - flatten the multidimensional array that is transform [[1,2],3,4] to [1,2,3,4] and then use the same logic used for single dimensional array.

Example:

 var a = [
   [1, 4], 2, 3
 ]
 var b = [2, 4, 5]
 var c = [2, 3, 6, [4, 7]]

 //flatten the array's

 //[1,4,2,3]
 var aFlattened = $.map(a, function(n) {
   return n;
 })

 //[2,4,5]
 var bFlattened = $.map(b, function(n) {
   return n;
 })

 //[2,3,6,4,7]
 var cFlattened = $.map(c, function(n) {
   return n;
 })

 var result = $.grep(aFlattened, function(value) {
   return (bFlattened.indexOf(value) > -1 && cFlattened.indexOf(value) > -1);
 });

 console.log(result);
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

Answer

// First this is how you declare an array
var a = [1,2,3];
var b = [2,4,5];
var c = [2,3,6];


// Second, this function should handle undetermined number of parameters (so arguments should be used)
function intersect(){
  var args = arguments;
  // if no array is passed then return empty array
  if(args.length == 0) return [];
  
  // for optimisation lets find the smallest array
  var imin = 0;
  for(var i = 1; i < args.length; i++)
    if(args[i].length < args[imin].length) imin = i;
  var smallest = Array.prototype.splice.call(args, imin, 1)[0];
  
  return smallest.reduce(function(a, e){
    for(var i = 0; i < args.length; i++)
      if(args[i].indexOf(e) == -1) return a;
    a.push(e);
    return a;
  }, []);
}

console.log(intersect(a, b, c));

Answer

First of all '{}' means Object in JavaScript.
Here is my suggestion.(this is another way of doing it)

// declarations  
var a = [1,2,3];  
var b = [2,4,5];  
var c = [2,3,6];  

// filter property of array
a.filter(function(val) {
    if (b.indexOf(val) > -1  && c.indexOf(val) > -1)
        return val;
});

what it does is it checks for each element in array 'a' and checks if that value is present in array 'b' and array 'c'. If it is true it returns the value. Simple!!!. The above code should work for String as well but it wouldn't work for IE < 9, so be careful.

Answer
// Intersecting 2 ordered lists of length n and m is O(n+m)
// This can be sped up by skipping elements
// The stepsize is determined by the ratio of lengths of the lists
// The skipped elements need to be checked after skipping some elements:
// In the case of step size 2 : Check the previous element
// In case step size>2 : Binary search the previously skipped range
// This results in the best case complexity of O(n+n), if n<m
// or the more propable complexity of O(n+n+n*log2(m/n)), if n<m
function binarySearch(array, value, start = 0, end = array.length) {
    var j = start,
        length = end;
    while (j < length) {
        var i = (length + j - 1) >> 1; // move the pointer to
        if (value > array[i])
            j = i + 1;
        else if (value < array[i])
            length = i;
        else
            return i;
    }
    return -1;
}
function intersect2OrderedSets(a, b) {
    var j = 0;
    var k = 0;
    var ratio = ~~(b.length / a.length) - 1 || 1;
    var result = [];
    var index;
    switch (ratio) {
        case 1:
            while (j < a.length) {
                if (a[j] === b[k]) {
                    result.push(a[j]);
                    j++;
                    k++;
                } else if (a[j] < b[k]) {
                    while (a[j] < b[k]) j++;
                } else {
                    while (b[k] < a[j]) k++;
                    if (k >= b.length) break;
                }
            }
            break;
        case 2:
            while (j < a.length) {
                if (a[j] === b[k]) {
                    result.push(a[j]);
                    j++;
                    k++;
                } else if (a[j] < b[k]) {
                    while (a[j] < b[k]) j++;
                } else {
                    while (b[k] < a[j]) k += 2;
                    if (k - 1 >= b.length) break;
                    if (a[j] <= b[k - 1]) k--;
                }
            }
            break;
        default:
            while (j < a.length) {
                if (a[j] === b[k]) {
                    result.push(a[j]);
                    j++;
                    k++;
                } else if (a[j] < b[k]) {
                    while (a[j] < b[k]) j++;
                } else {
                    while (b[k] < a[j]) k += ratio;
                    index = binarySearch(b, a[j], k - ratio + 1, k + 1 < b.length ? k + 1 : b.length - 1);
                    if (index > -1) {
                        result.push(a[j]);
                        j++;
                        k = index + 1;
                    } else {
                        j++;
                        k = k - ratio + 1;
                    }
                    if (k >= b.length) break;
                }
            }
    }
    return result;
}

function intersectOrderedSets() {
    var shortest = 0;
    for (var i = 1; i < arguments.length; i++)
        if (arguments[i].length < arguments[shortest].length) shortest = i;
    var result = arguments[shortest];
    for (var i = 0, a, b, j, k, ratio, index; i < arguments.length; i++) {
        if (result.length === 0) return result;
        if (i === shortest) continue;
        a = result;
        b = arguments[i];
        result = intersect2OrderedSets(a, b);
    }
    return result;
}

How to use:

intersectOrderedSets(a,b,c);

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.