JS 세트

Oskars Sylwan에 Unsplash의 사진

자바스크립트 객체는 훌륭합니다! 그러나 약간 원시적입니다.

javascript 객체는 고려해야 할 힘입니다. 매우 다재다능하며 간단한 키 값 쌍을 저장하기에 좋은 장소입니다.
추적할 캐릭터가 있습니까? 개체를 사용합니다. 추적할 숫자가 있습니까? 개체를 사용합니다. 추적할 노드가 있습니까? 잘...

자바스크립트 세트

다시 {} 간단한 키 값 쌍에 적합합니다. 키는 항상 정말 간단합니다. 문자열 또는 숫자인 경우 문자열로 변환됩니다. 이것은 일반적으로 문제가 없으며 저장하는 값은 함수나 다른 객체처럼 여전히 복잡할 수 있습니다.

키를 더 복잡하게 만들려는 경우에만 문제가 됩니다.

나는 두 개의 연결 목록에 공통된 교차점이 있는지 확인하고자 하는 약간의 코딩 알고리즘을 해결하고 있었습니다.

/*
  Intersecting
  2 - 3 - 7 \ 
            4 - 5 - 3
    9 - 10 /

  Not intersecting
  2 - 3 - 7

  9 - 3
*/

내가 생각한 한 가지는 문자열이나 숫자와 관련된 많은 문제에서 이 패턴을 키로 사용했기 때문에 하나를 반복하고 모든 참조를 저장할 수 있다는 것입니다.

문제는 linkedList가 노드로 구성되어 있어 복잡한 값이라는 것입니다. data 속성만 비교한다면 괜찮겠지만 데이터 값이 같은 노드가 아니라 정확히 같은 노드인지 알고 싶었다.

// Ex Node:
node = {
  data:4,
  next: nextNode
}

세트

빨리 머리 위로. 이것은 이 문제를 해결하는 가장 효율적인 방법이 아닙니다. 집합의 조회는 O(n) 일 수 있지만 복잡한 데이터 구조를 저장할 수 있습니다. 전반적으로 내가 말하는 솔루션은 O(n^2) 시간 복잡성이었습니다. 하나의 목록을 저장한 다음 다른 목록을 반복하고 집합에서 조회를 수행하기 때문입니다. 실제로 그 당시에는 더 나은 솔루션을 만들었지만 나중에 유용할 수 있기 때문에 세트로 실제로 구현하고 싶었습니다.

function inefficientIntersectingLists(ll1, ll2) {
  let firstNode = ll1
  let secondNode = ll2
  const setOfNodes = new Set()

  // insert into our set
  while (firstNode !== null) {
    setOfNodes.add(firstNode)
    firstNode = firstNode.next
  }
  // loop through second linkedList check for overlap
  while (secondNode !== null) {
    if (setOfNodes.has(secondNode)) {
      return secondNode
    }
    secondNode = secondNode.next
  }
  return 'No overlap'
}

구현

설정하기 쉽습니다. 😁.

  const setOfNodes = new Set()

이것을 레퍼토리에 추가할 수 있습니다.

  setOfNodes.add(firstNode)

키가 복잡해야 하는 경우 Set에 필요한 것이 있습니다.

  setOfNodes.has(secondNode)

테이크아웃

키로 저장하려는 복잡한 값이 있는 경우 집합을 사용하십시오. strings 및 numbers 와 같은 기본 값을 처리하는 경우 조회 시간이 일정하므로 O(1) 객체를 사용하십시오. 다음은 MDN 에서 set 메서드에 대한 추가 정보입니다.

집합에 대해 전혀 신경 쓰지 않지만 이제 연결 목록 겹침 문제에 대한 보다 최적의 솔루션을 보려면 확인하십시오here.

읽어주셔서 감사합니다. 조만간 이 사용 사례를 찾을 수 있을 것입니다.

해피코딩,

제임스