一道看似简单的阿里前端算法题
题目描述
题目分析
我们以下面这个数组为例，我们首先要明白题目中的第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。
链接：https://juejin.cn/post/7001397295912583198
