博主本次介绍的题目是真实来自阿里前端CBU部门招聘实习生的一道前端算法题，这道题并不是LeetCode上的找出数组中第K大的元素这道题模，而是在这道题目的基础上进行了改编，让我们一起来探索下这道题目该如何解决。
题目描述
题目分析
我们以下面这个数组为例，我们首先要明白题目中的第2大的元素指的是4，第3大的元素指的是3，也就是说指的是去重后的数组中的排序。我们之所以要建立一个哈希表是因为我们需要知道第k大和第m大的元素总共出现了几次，因为最后需要进行求和。
[1, 2, 4, 4, 3, 5] 复制代码
解题思路
本题博主采用的是哈希表 + 堆排序的方式来求解。
第一步：构建哈希表，键为目标元素，值为目标元素出现的次数
const map = new Map(); for (let v of arr) { if (!map.get(v)) { map.set(v,1); } else { map.set(v,map.get(v) + 1) } } 复制代码
第二步：对数组去重
const singleNums = [...new Set(arr)] 复制代码
第三步：构建大顶堆
// 堆的尺寸指的是去重后的数组 let heapSize = singleNums.length; buildMaxHeap(singleNums, heapSize); function buildMaxHeap(arr, heapSize) { // 从最后一个叶子节点开始进行堆化 for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { // 进行堆化 maxHeapify(arr, i, heapSize); } } function maxHeapify(arr, i, heapSize) { // 首先假定第i个是最大的 let max = i; let leftChild = 2 * i + 1; let rightChild = 2 * i + 2; // 如果下标不越界，并且左孩子的比最大值大则更新最大值 if (leftChild < heapSize && arr[leftChild] > arr[max]) { max = leftChild; } if (rightChild < heapSize && arr[rightChild] > arr[max]) { max = rightChild; } if (max !== i) { swap(arr, i, max); // 上来的元素的位置往下要接着堆化 maxHeapify(arr, max, heapSize); } } // 交换数组中两个元素 function swap(nums, a, b) { let temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } 复制代码
第四步：求第k大的元素和第m大元素
function target(arr, x) { for (let i = 0; i < x - 1; i++) { // 交换不需要进行堆化的元素 if (i === min - 1) result.push(arr[0]); swap(arr, 0, arr.length - 1 - i); arr heapSize--; maxHeapify(arr, 0, heapSize) } } target(singleNums, max) result.push(singleNums[0]); 复制代码
第五步：根据哈希表出现的次数计算并返回结果
return result.reduce((pre,cur) => pre + cur * map.get(cur),0) 复制代码
AC代码
/* * @Author: FaithPassion * @Date: 2021-07-09 10:06:00 * @LastEditTime: 2021-08-28 11:09:30 * @Description: 找出数组中第k大和第m大的数字相加之和 * let arr = [1,2,4,4,3,5], k = 2, m = 4 * findTopSum(arr, k, m); // 第2大的数是4，出现2次，第4大的是2，出现1次，所以结果为10 */ /** * @description: 采用堆排序求解 * @param {*} arr 接收一个未排序的数组 * @param {*} k 数组中第k大的元素 * @param {*} m 数组中第m大的元素 * @return {*} 返回数组中第k大和第m大的数字相加之和 */ function findTopSum(arr, k, m) { function buildMaxHeap(arr, heapSize) { // 从最后一个叶子节点开始进行堆化 for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { // 进行堆化 maxHeapify(arr, i, heapSize); } } // 最大堆化函数 function maxHeapify(arr, i, heapSize) { // 首先假定第i个是最大的 let max = i; let leftChild = 2 * i + 1; let rightChild = 2 * i + 2; // 如果下标不越界，并且左孩子的比最大值大则更新最大值 if (leftChild < heapSize && arr[leftChild] > arr[max]) { max = leftChild; } if (rightChild < heapSize && arr[rightChild] > arr[max]) { max = rightChild; } if (max !== i) { swap(arr, i, max); // 上来的元素的位置往下要接着堆化 maxHeapify(arr, max, heapSize); } } // 交换数组中两个元素 function swap(nums, a, b) { let temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } let result = [] // k和m中较大的 let max = Math.max(k, m); // k和m中较小的 let min = Math.min(k, m); const map = new Map(); for (let v of arr) { if (!map.get(v)) { map.set(v,1); } else { map.set(v,map.get(v) + 1) } } // 求第x大的元素 function target(arr, x) { for (let i = 0; i < x - 1; i++) { // 交换不需要进行堆化的元素 if (i === min - 1) result.push(arr[0]); swap(arr, 0, arr.length - 1 - i); arr heapSize--; maxHeapify(arr, 0, heapSize) } } const singleNums = [...new Set(arr)] // 堆的大小 let heapSize = singleNums.length; // 构建大顶堆 buildMaxHeap(singleNums, heapSize); target(singleNums, max) result.push(singleNums[0]); return result.reduce((pre,cur) => pre + cur * map.get(cur),0) } findTopSum([1, 2, 4, 4, 3, 5], 2, 4) 复制代码
题目反思
- 学会通过堆排序的方式来求解Top K问题。
- 学会对数组进行去重。
- 学会使用reduce Api。