이것은 최적의 솔루션일 수도 있고 아닐 수도 있습니다. 내 솔루션을 맹목적으로 암기하지 마십시오.

매주 newsletter .

대상: js에 익숙한 사람들(피드백 부탁드립니다!)

이번주 질문:

You’re given two integer arrays (n and m), and an integer k. Using the digits from n and m, return the largest number you can of length k.

예시:

n = [3,4,6,5]
m = [9,0,2,5,8,3]
k = 5
$ maxNum(n, m, k)
$ 98655

이 질문을 처음 읽었을 때 가장 확실한 해결책은 배열을 결합한 다음 정렬하는 것이었습니다. 처음 k개의 숫자가 답이 될 것입니다. 다음과 같이 일부 기능적 기능을 함께 연결할 수 있습니다.

const maxNum = (n, m, k) =>
  [...n, ...m]
    .sort((a, b) => b - a)
    .filter((_, i) => i < k)
    .join("");

이것이 하는 일은 n과 m(O(n+m))을 펼치고 내림차순으로 정렬한 다음 O(n+m log n+m), 필터링(O(n+m)) 및 결합(O)입니다. (k)) 이것은 O(n+m log n+m)의 복잡도를 제공합니다. 이 동일한 논리를 보다 효율적으로 구현하는 방법은 여러 가지가 있지만 병목 현상은 정렬입니다.

다음 아이디어는 가장 큰 K 값만 필요하고 정렬은 필요하지 않다는 것을 확인함으로써 떠올랐습니다. 이는 힙과 같이 상각 비용이 더 나은 일부 데이터 구조를 사용할 수 있음을 의미합니다. 다음은 힙의 배열 구현입니다.

function MaxHeap() {
  this.heap = [];
  function getChildrenIndex(curr) {
    return [2 * curr + 1, 2 * curr + 2];
  }
  function getParentIndex(curr) {
    return curr % 2 === 0 ? (curr - 2) / 2 : (curr - 1) / 2;
  }

  return {
    heap: this.heap,
    insert: function (value) {
      let { heap } = this;
      heap.push(value);
      let currIndex = heap.length - 1;
      let parentIndex = getParentIndex(currIndex);
      while (heap[currIndex] > heap[parentIndex]) {
        const tmp = heap[parentIndex];
        heap[parentIndex] = heap[currIndex];
        heap[currIndex] = tmp;
        currIndex = parentIndex;
        parentIndex = getParentIndex(currIndex);
      }
    },
    remove: function () {
      let { heap } = this;
      const lastItem = heap.pop();
      let currIndex = 0;
      let [l, r] = getChildrenIndex(currIndex);
      const returnVal = heap[0];
      heap[0] = lastItem;
      while (heap[currIndex] < heap[l] || heap[currIndex] < heap[r]) {
        const tmp = heap[currIndex];
        if (heap[r] > heap[l]) {
          heap[currIndex] = heap[r];
          heap[r] = tmp;
          currIndex = r;
        } else {
          heap[currIndex] = heap[l];
          heap[l] = tmp;
          currIndex = l;
        }
        [l, r] = getChildrenIndex(currIndex);
      }
      return returnVal;
    }
  };
}

그런 다음 드라이버 함수는 평균 O(1)의 삽입(O(n+m))을 사용하여 반복적으로 n과 m을 힙에 추가한 다음 k 항목(O(k))을 제거합니다. O(n+m)이지만 최악의 경우는 이전 솔루션보다 좋지 않습니다.

const maxNum = (n, m, k) => {
  let h = new MaxHeap();
  n.forEach((item) => h.insert(item));
  m.forEach((item) => h.insert(item));
  return Array(k)
    .fill(0)
    .map((_) => h.remove())
    .join("");
};

마침내 내 생각은 문제 그 자체로 갔다. 입력이 숫자이기 때문에 최대 10개의 다른 입력 값이 있을 수 있다는 것을 알고 있습니다. 이를 통해 일부 비비교 정렬을 수행할 수 있지만 숫자를 세는 것만으로도 기수 정렬만큼 복잡한 것은 필요하지 않습니다. . 이 솔루션은 기본적으로 모든 자릿수(O(n+m))를 계산한 다음 카운트(O(10) = O(1))를 거친 다음 문자열을 재조립합니다. O(n+m) 시간 복잡도와 거의 일정한 공간을 제공합니다.

const linearMaxNum = (n, m, k) => {
  const count = {};
  let res = "";
  let all = [...n, ...m];
  all.forEach((item) => {
    if (!count[item]) {
      count[item] = 0;
    }
    count[item]++;
  });
  for (let i = 9; i >= 0; i--) {
    res += new Array(count[i]).fill(i).join("");
  }
  return res.substr(0, k);
};