Algorithm and Data Structure勉強 01-Frequency Problem

Problem Description

Write a function that two arrays as parameters,and then return an array that is the　intersection of these two arrays.For example,Interscrion([1,2,3],[7,3,4,1])should return [1,3].

直感的に、配列中にひとつずつを探す、同じの数字をまとめると、解決でき思う。

解答一

function interaction(arr1, arr2){
   let result = []
   for(let i=0;i < arr1.length;i++){
     for(let j=0;j < arr1.length;j++){
	if(arr1[i] === arr2[j]){
	  result.push(arr1[i]);
	}
     }
   }
   console.log(result);
   return result;
}
interaction([1,2,3],[5,6,3,4,5])

しかし、複雑度O(n*m)、そして、別の早方法が探そう。
まず、配列の数字を計数し、複数以上の数字まとめば、これが結果と思う。

解答二

function interaction(arr1,arr2){
  let result = [];
  let arr3 = arr1.concat(arr2);
  let counter = {};
  
  for(let i=0;i < arr3.length;i++){
    if(!counter[arr3[i]]){
      counter[arr3[i]] = 1;
    }else{
      counter[arr3[i]]++;
    }
  }
  
  for(let property in counter){
   if(counter[property] >= 2){
     result.push(property);
   }
  }
  console.log(result);
  return result;
}

複雑度O(n+m)をなります。