[数据结构与算法]前k个高频元素(用堆优化) JavaScript

刺骨的言语ヽ痛彻心扉 2022-12-12 04:39 106阅读 0赞

### 题目：前k个高频元素 ###

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:
    
    输入: nums = [1,1,1,2,2,3], k = 2
    输出: [1,2]
    示例 2:
    
    输入: nums = [1], k = 1
    输出: [1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。  
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。  
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。  
你可以按任意顺序返回答案。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/top-k-frequent-elements

### 解题： ###

##### 1.利用字典map配合sort排序： #####

/** * @param {number[]} nums * @param {number} k * @return {number[]} */
        var topKFrequent = function (nums, k) { 
          const map = new Map()
          nums.forEach((item) => { 
            if (!map.has(item)) { 
              map.set(item, 1)
            } else { 
              map.set(item, 1 + map.get(item))
            }
          })
          let res = Array.from(map).sort((a, b) => { 
            return b[1] - a[1]
          })
          res = res.slice(0, k).map(([a, b]) => a)
          return res
        };

这种方法进行了sort排序，所以时间复杂度一定大于nlogn，我们有没有办法优化呢？答案是有的。  
因为题目中要求对前k个元素进行排序，而我们上面这种方法实际上是对所有元素进行排序了，并且题目的提示中告诉我们“你可以按任意顺序返回答案”，其实也是在暗示我们用堆这个数据结构了

##### 1.利用字典map配合堆进行优化： #####

// 引入堆数据结构，堆实现参考https://blog.csdn.net/qq_43540219/article/details/108932367
    // 但是注意要改造一下比较的部分,改为比较.value,并且要加一个判断条件保证比较的子/父节点存在,因为我们传进去的不是一个数字,而是一个键值对
          shiftUp(index) { 
            if (index === 0) { 
              return
            }
            const parentIndex = this.getParentIndex(index)
            if (this.heap[parentIndex]/*新增代码*/ && this.heap[parentIndex].value/*新增代码*/ > this.heap[index].value/*新增代码*/) { 
              this.swap(parentIndex, index);
              this.shiftUp(parentIndex)
            }
          }
          shiftDown(index) { 
            const leftIndex = this.getLeftIndex(index)
            const rightIndex = this.getRightIndex(index)
            if (this.heap[leftIndex]/*新增代码*/ && this.heap[leftIndex].value/*新增代码*/ < this.heap[index].value/*新增代码*/) { 
              this.swap(leftIndex, index)
              this.shiftDown(leftIndex)
            }
            if (this.heap[rightIndex]/*新增代码*/ && this.heap[rightIndex].value/*新增代码*/ < this.heap[index].value/*新增代码*/) { 
              this.swap(rightIndex, index)
              this.shiftDown(rightIndex)
            }
          }
    // 下面是算法部分(维护一个大小为k的最小堆)
        var topKFrequent = function (nums, k) { 
          const map = new Map()
          nums.forEach((item) => { 
            if (!map.has(item)) { 
              map.set(item, 1)
            } else { 
              map.set(item, 1 + map.get(item))
            }
          })
          const h = new MinHeap()
          map.forEach((value, key) => { 
            h.insert({ 
              value,
              key
            })
            if (h.size() > k) { 
              h.pop()
            }
          })
          return h.heap.map(a => a.key)
        }

此时时间复杂度降为O(nlogk) // k为“前k个高频元素”堆的大小  
空间复杂度因为维护了一个map，为n，维护了一个堆为k，k最坏情况下=n  
所以空间复杂度为n+k=》 仍然为O(n)