一道看似簡單的阿裡前端算法題

部落客本次介紹的題目是真實來自阿裡前端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。