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が比較的小さい場合に特に有効です。