BFE.devでのAI解答例 - JavaScript コーディング問題
152. 上位k個の要素を返す

解答例:

以下は、ソートアルゴリズムを使用してこの問題を解決する方法です。

function topK(nums, k) {
  nums.sort((a, b) => b - a); // 降順にソートする
  return nums.slice(0, k); // 上位k個を返す
}

このアルゴリズムの時間複雑度はO(nlogn)で、空間複雑度はO(1)です。よって、比較的効率的に問題を解決できます。

より効率的なアルゴリズムには、最小ヒープを使用する方法があります。このアルゴリズムの時間複雑度はO(nlogk)で、空間複雑度はO(k)です。

function topK(nums, k) {
  const heap = [];
  nums.forEach(num => {
    if (heap.length < k) {
      heap.push(num);
      if (heap.length === k) {
        buildHeap(heap);
      }
    } else if (num > heap[0]) {
      heap[0] = num;
      heapify(heap, 0);
    }
  });
  return heap;
}

function buildHeap(arr) {
  const n = arr.length;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, i);
  }
}

function heapify(arr, i) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let maxIndex = i;
  if (left < arr.length && arr[left] < arr[maxIndex]) {
    maxIndex = left;
  }
  if (right < arr.length && arr[right] < arr[maxIndex]) {
    maxIndex = right;
  }
  if (maxIndex !== i) {
    [arr[i], arr[maxIndex]] = [arr[maxIndex], arr[i]];
    heapify(arr, maxIndex);
  }
}

このアルゴリズムは、最初に上位k個の数を配列に追加し、この配列を最小ヒープデータ構造に変換することによって始まります。それから、各数値に対して、最小ヒープのルート要素と比較し、必要に応じて要素を交換し、ヒープの性質を保ちます。最後に、ヒープ内の要素を返します。

このアルゴリズムは、配列が非常に大きい場合に有効で、kが比較的小さい場合に特に有効です。