우리는 두 개의 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]