The topic introduced by the blogger this time is a real front-end algorithm problem recruited by the CBU department of Alibaba. This problem is not the problem model of finding the KTH element in the array in LeetCode, but is adapted based on this problem. Let’s explore how to solve this problem together.

Topic describes

Subject analysis

Let’s take the following array as an example. We need to understand that the second largest element in the list refers to 4 and the third largest element refers to 3. And the reason why we want to build a hash table is because we need to know how many times the KTH and MTH elements occur, because we need to sum them up at the end.

[1.2.4.4.3.5]
Copy the code

Their thinking

In this case, the blogger uses hash table + heap sort to solve.

Step 1: Build a hash table with the key as the target element and the value as the number of occurrences of the target element

const map = new Map(a);for (let v of arr) {
    if(! map.get(v)) { map.set(v,1);
    } else {
        map.set(v,map.get(v) + 1)}}Copy the code

Step 2: Undo the array

const singleNums = [...new Set(arr)]
Copy the code

Step 3: Build the big top heap

// The size of the heap refers to the deduplicated array
let heapSize = singleNums.length;
buildMaxHeap(singleNums, heapSize);
function buildMaxHeap(arr, heapSize) {
    // Heap from the last leaf node
    for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
        // heapmaxHeapify(arr, i, heapSize); }}function maxHeapify(arr, i, heapSize) {
    // First assume that the ith is the largest
    let max = i;
    let leftChild = 2 * i + 1;
    let rightChild = 2 * i + 2;
    // If the subscript does not exceed the bounds and the left child is larger than the maximum, the maximum is updated
    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);// The position of the top element should be heaped downmaxHeapify(arr, max, heapSize); }}// Swap two elements of the array
function swap(nums, a, b) {
    let temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}
Copy the code

Step 4: Find the KTH and MTH largest elements

function target(arr, x) {
    for (let i = 0; i < x - 1; i++) {
        // Swap elements that do not need to be heaped
        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]);
Copy the code

Step 5: Calculate and return the result based on the number of occurrences of the hash table

return result.reduce((pre,cur) = > pre + cur * map.get(cur),0)
Copy the code

AC code

/* * @Author: FaithPassion * @Date: 2021-07-09 10:06:00 * @LastEditTime: 2021-08-28 11:09:30 * @Description: Let arr = [1,2,4,4,3,5], k = 2, m = 4 * findTopSum(arr, k, m); // The second largest number is 4, which occurs twice, and the fourth largest number is 2, which occurs once, so the result is 10 */

/ * * *@description: Use heap sort to solve *@param {*} Arr receives an unsorted array *@param {*} The KTH largest element in the k array *@param {*} The MTH element in the m array *@return {*}  Returns the sum of the KTH and MTH largest digits in the array */
function findTopSum(arr, k, m) {
    

    function buildMaxHeap(arr, heapSize) {
        // Heap from the last leaf node
        for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
            // heapmaxHeapify(arr, i, heapSize); }}// Maximum heap function
    function maxHeapify(arr, i, heapSize) {
        // First assume that the ith is the largest
        let max = i;
        let leftChild = 2 * i + 1;
        let rightChild = 2 * i + 2;
        // If the subscript does not exceed the bounds and the left child is larger than the maximum, the maximum is updated
        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);// The position of the top element should be heaped downmaxHeapify(arr, max, heapSize); }}// Swap two elements of the array
    function swap(nums, a, b) {
        let temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
    let result = []
    // the larger of k and m
    let max = Math.max(k, m);
    // smaller of k and m
    let min = Math.min(k, m);
    const map = new Map(a);for (let v of arr) {
        if(! map.get(v)) { map.set(v,1);
        } else {
            map.set(v,map.get(v) + 1)}}// Find the x-th element
    function target(arr, x) {
        for (let i = 0; i < x - 1; i++) {
            // Swap elements that do not need to be heaped
            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)]
    // The heap size
    let heapSize = singleNums.length;
    // Build the big top heap
    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)
Copy the code

The title to reflect

  • Learn how to solve Top K problems by heap sorting.
  • Learn how to de-duplicate arrays.
  • Learn to use the Reduce Api.