力扣題目鏈接

為武鳴等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及武鳴網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站設(shè)計(jì)制作、網(wǎng)站設(shè)計(jì)、武鳴網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

題目:

給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。

示例 1:

• 輸入: nums = [1,1,1,2,2,3], k = 2
• 輸出: [1,2]

示例 2:

• 輸入: nums = [1], k = 1
• 輸出: [1]

提示：

• 你可以假設(shè)給定的 k 總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個(gè)數(shù)。
• 你的算法的時(shí)間復(fù)雜度必須優(yōu)于 $O(n \log n)$ , n 是數(shù)組的大小。
• 題目數(shù)據(jù)保證答案唯一，換句話說(shuō)，數(shù)組中前 k 個(gè)高頻元素的集合是唯一的。
• 你可以按任意順序返回答案。

因?yàn)閖s沒(méi)有小頂堆(用數(shù)組構(gòu)造的一棵遞增的二叉樹(shù),數(shù)組頭部就是最小值),所以需要自己構(gòu)造:

構(gòu)建小頂堆涉及的節(jié)點(diǎn)關(guān)系公式:

假設(shè)節(jié)點(diǎn)索引為n(n>=0):

父節(jié)點(diǎn): n-1/2

左子節(jié)點(diǎn): 2n+1

右子節(jié)點(diǎn): 2n+2

class Heap {
        constructor(compareFn) {
          this.compareFn = compareFn
          this.queue = []
        }

        // 添加
        push(item) {
          // 推入元素
          this.queue.push(item)

          // 上浮
          let index = this.size() - 1 // 記錄推入元素下標(biāo)
          let parent = Math.floor((index - 1) / 2) // 記錄父節(jié)點(diǎn)下標(biāo)

          // 注意compare參數(shù)順序
          while (parent >= 0 && this.compare(parent, index) >0) {
            ;[this.queue[index], this.queue[parent]] = [
              this.queue[parent],
              this.queue[index],
            ]

            // 更新下標(biāo)
            index = parent
            parent = Math.floor((index - 1) / 2)
          }
        }

        // 獲取堆頂元素并移除
        pop() {
          // 堆頂元素
          const out = this.queue[0]

          // 移除堆頂元素 填入最后一個(gè)元素
          this.queue[0] = this.queue.pop()

          // 下沉
          let index = 0 // 記錄下沉元素下標(biāo)
          let left = 1 // left 是左子節(jié)點(diǎn)下標(biāo) left + 1 則是右子節(jié)點(diǎn)下標(biāo)
          let searchChild = this.compare(left, left + 1) >0 ? left + 1 : left // 從左右子葉找出一個(gè)較小的值進(jìn)行比較
          // 如果下沉節(jié)點(diǎn)要大于子節(jié)點(diǎn) 則交換位置
          while (
            searchChild !== undefined &&
            this.compare(index, searchChild) >0
          ) {
            // 注意compare參數(shù)順序
            ;[this.queue[index], this.queue[searchChild]] = [
              this.queue[searchChild],
              this.queue[index],
            ]

            // 更新下標(biāo)
            index = searchChild
            left = 2 * index + 1
            searchChild = this.compare(left, left + 1) >0 ? left + 1 : left // 重新比較出左右子葉較小的一個(gè)供下一輪循環(huán)進(jìn)行比較
          }

          return out
        }

        size() {
          return this.queue.length
        }

        // 使用傳入的 compareFn 比較兩個(gè)位置的元素
        compare(index1, index2) {
          // 處理下標(biāo)越界問(wèn)題
          if (this.queue[index1] === undefined) return 1
          if (this.queue[index2] === undefined) return -1

          return this.compareFn(this.queue[index1], this.queue[index2])
        }
      }

有小頂堆后就可以用在題目里了:

  const topKFrequent = function (nums, k) {
        const map = new Map() // 創(chuàng)建哈希表
        // 以key為num value為num出現(xiàn)的次數(shù)存入哈希表
        for (const num of nums) {
          map.set(num, (map.get(num) || 0) + 1)
        }

        // 創(chuàng)建小頂堆
        const heap = new Heap((a, b) =>a[1] - b[1]) // a-b從小到大 類似sort函數(shù)
        // entry 是一個(gè)長(zhǎng)度為2的數(shù)組，0位置存儲(chǔ)key，1位置存儲(chǔ)value [[num, frequent]]
        for (const entry of map.entries()) {
          heap.push(entry)
          // 當(dāng)堆大小滿足k時(shí) 則開(kāi)始pop 堆里只保留topk
          if (heap.size() >k) {
            heap.pop()
          }
        }
        const result = []
        // 小頂堆pop出來(lái)的就是最小值 一個(gè)個(gè)pop出來(lái) res數(shù)組從后往前放 這樣就是從大到小的順序了
        for (let i = heap.size() - 1; i >= 0; i--) {
          result[i] = heap.pop()[0]
        }

        return result
      }
      console.log(topKFrequent([1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 6, 6, -1], 3)) // [3,2,6]

不用小頂堆的做法,直接懟map.entries()進(jìn)行排序:

  function topKFrequent2(nums, k) {
        const map = new Map() // 創(chuàng)建哈希表
        // 以key為num value為num出現(xiàn)的次數(shù)存入哈希表
        for (const num of nums) {
          map.set(num, (map.get(num) || 0) + 1)
        }
        const result = [...map.entries()]
          .sort((a, b) =>b[1] - a[1]) // 按照value排序
          .slice(0, k) // 獲取前k個(gè)元素
          .map((e) =>e[0]) // 返回num的集合

        return result
      }
      console.log(topKFrequent2([1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 6, 6, -1], 3)) // [3,2,6]

代碼隨想錄鏈接

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：LeetCode347前k個(gè)高頻元素js-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://weahome.cn/article/pgsdi.html