Computer >> 컴퓨터 >  >> 프로그램 작성 >> JavaScript

두 배열의 교차 JavaScript

<시간/>

우리는 두 개의 Number 배열을 가지고 있고, 그것들의 교집합을 계산하고 임의의 순서로 교차하는 요소를 포함하는 배열을 반환하는intersection()과 같은 함수를 작성해야 합니다. 결과의 각 요소는 두 배열에 표시되는 횟수만큼 표시되어야 합니다.

예를 들어 - 만약,

Input: arr1 = [1,2,3,1], arr2 = [1,3,1]
Output: [1,3,1]

접근

배열이 정렬되어 있었다면 초기에 각각의 배열의 시작을 0으로 가리키고 두 포인터 접근 방식을 사용할 수 있었고 해당 포인터를 증가시키면서 O(m+n) 복소수 w.r.t가 되었을 것입니다. 여기서 m과 n은 배열의 크기입니다.

그러나 정렬되지 않은 배열이 있으므로 배열을 정렬한 다음 이 접근 방식을 사용하는 데 논리가 없으므로 첫 번째 값과 두 번째 값을 모두 확인하고 교차 배열을 구성합니다. O(n^2) 시간이 소요됩니다.

그리고 이것을 하기 위한 코드는 -

가 될 것입니다.

예시

const arr1 = [1, 2, 43, 5, 3, 7, 7,8, 4, 2];
const arr2 = [1, 1, 6, 6, 2, 78, 7, 2, 3, 7, 23, 5, 3];
const intersection = (arr1, arr2) => {
   const res = [];
   const { length: len1 } = arr1;
   const { length: len2 } = arr2;
   const smaller = (len1 < len2 ? arr1 : arr2).slice();
   const bigger = (len1 >= len2 ? arr1 : arr2).slice();
   for(let i = 0; i < smaller.length; i++){
      if(bigger.indexOf(smaller[i]) !== -1){
         res.push(smaller[i]);
         bigger.splice(bigger.indexOf(smaller[i]), 1, undefined);
      }
   };
   return res;
};
console.log(intersection(arr1 ,arr2));

출력

콘솔의 출력은 -

[1, 2, 5, 3, 7, 7, 2]