찾다

 >  Q&A  >  본문

javascript - 교차점을 뺀 두 배열의 합집합을 찾는 좋은 알고리즘은 무엇입니까?

으아악

중복 요소를 제거한 후 두 배열의 병합된 배열을 찾습니다(양쪽의 중복 요소를 삭제하는 것을 말합니다. 예를 들어 3이 반복되면 결과에 3이 나올 수 없으며 이는 배열 중복 제거와 다릅니다). 합집합에서 배열 부분의 교차점을 뺀 부분인데, 이 부분에 수학적 이름이 있는지 모르겠습니다. 시간 복잡도가 낮은 알고리즘을 찾고 계십니까?

过去多啦不再A梦过去多啦不再A梦2706일 전1516

모든 응답(6)나는 대답할 것이다

  • 大家讲道理

    大家讲道理2017-06-26 10:53:43

    set를 인덱스로 사용한 다음 더 짧은 O(n)을 탐색합니다

    으아악

    회신하다
    0
  • 为情所困

    为情所困2017-06-26 10:53:43

    두 세트에서 겹치지 않는 부분을 찾으려면 먼저 두 세트의 합집합을 찾은 다음 공통 요소를 제거하면 됩니다.
    A∪B - A∩B = { x | (x∈A & x∉B) || (x∉A & x∈B) }

    프로그램 아이디어를 사용한 구현은 다음과 같습니다.
    두 배열을 병합한 다음 필터 메서드를 사용하여 배열 a와 b의 교차 요소를 필터링합니다. a가 b에 없고 b가 a에 없는 a.concat(b)의 요소를 필터링합니다. 주로 배열에 요소가 포함되어 있는지 판단하는 작업이 포함됩니다. Array.prototype.indexOf, Set의 has 메서드, Array.prototype.includes의 세 가지 구현 방법이 있습니다.

    NaN을 고려하지 않고 ES5의 indexOf 메소드를 사용한 구현 방법:

    으아악

    ES6의 새로운 Set 컬렉션 메소드를 사용하고 이를 필터 메소드와 결합하여 병합된 배열을 필터링합니다.

    으아악

    ES7의 새로운 Array.prototype.includes 배열 메소드를 사용하여 배열에 지정된 요소가 포함되어 있는지 여부를 반환하고 이를 필터 메소드와 결합하여 병합된 배열을 필터링합니다.

    으아악

    회신하다
    0
  • 伊谢尔伦

    伊谢尔伦2017-06-26 10:53:43

    이 결과를 대칭 차이라고 하며 집합 또는 다중 집합에 정의됩니다

    복잡성... 평균 O(n)

    회신하다
    0
  • 仅有的幸福

    仅有的幸福2017-06-26 10:53:43

    으아악

    ------------질문을 잘못 읽었습니다. 답도 틀렸습니다. 위의 내용은 중복된 내용을 제거한 것입니다. 아래를 참조하세요.------------

    ------------기본 for 루프만 순회하면 완료할 수 있습니다---------------

    으아악

    회신하다
    0
  • 黄舟

    黄舟2017-06-26 10:53:43

    첫 번째 방법은 for

    으아악

    두 번째 유형인 연결 및 필터는 중복된 항목을 병합한 후 제거하는 것이 원칙입니다

    으아악

    회신하다
    0
  • 女神的闺蜜爱上我

    女神的闺蜜爱上我2017-06-26 10:53:43

    객체의 속성을 활용하여 구현

    으아악

    스크린샷

    회신하다
    0
  • 취소회신하다