上一主题 下一主题
ScriptCat,新一代的脚本管理器脚本站,与全世界分享你的用户脚本油猴脚本开发指南教程目录
返回列表 发新帖

JavaScript大根堆建队On复杂度

[复制链接]
  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5895

    回帖

    6714

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6714

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-11 08:25:06 | 显示全部楼层 | 阅读模式

    只实现了一些基础的函数
    图片.png

    class MaxHeadp {
        heap
        border
        constructor(nums) {
            this.heap = nums;
            this.border = nums.length - 1
            this.initHeap();
        }
        initHeap() {
            const endIndex = this.getTopNode(this.border)
            for (let index = endIndex; index >= 0; index--) {
                this.downNode(index)
            }
        }
        haveNum() {
            return this.border + 1
        }
        pop() {
            if (this.border === -1) {
                return undefined
            }
            const temp = this.heap[0];
            this.heap[0] = this.heap[this.border];
            this.border--;
            this.downNode(0)
            return temp
        }
        swap(x, y) {
            let temp = this.heap[x]
            this.heap[x] = this.heap[y]
            this.heap[y] = temp
        }
        downNode(index) {
            let left = this.getLeftNode(index);
            let right = this.getRightNode(index);
            while (left <= this.border || right <= this.border) {
                let maxIndex = undefined
                if (left <= this.border || right <= this.border) {
                    maxIndex = this.heap[left] < this.heap[right] ? right : left
                } else {
                    maxIndex = left <= this.border ? right : left
                }
                if (this.heap[index] < this.heap[maxIndex]) {
                    this.swap(index, maxIndex)
                    index = maxIndex
                    left = this.getLeftNode(index);
                    right = this.getRightNode(index);
                } else {
                    break;
                }
            }
        }
        getTopNode(index) {
            return Math.floor((index - 1) / 2)
        }
        getLeftNode(index) {
            return (index + 1) * 2 - 1
        }
        getRightNode(index) {
            return (index + 1) * 2
        }
    }
    
    var findKthLargest = function (nums, k) {
        const heap = new MaxHeadp(nums)
        let times = 0
        let lastNum = undefined
        while (heap.haveNum() != 0) {
            const num = heap.pop()
            if (num !== lastNum) {
                times++
            }
            if (times == k) {
                return num
            }
        }
        return -1
    };
    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。

    该用户从未签到

    0

    主题

    25

    回帖

    20

    积分

    助理工程师

    积分
    20
    发表于 2024-9-11 09:20:44 | 显示全部楼层
    道长还重视算法练习hh
    回复

    使用道具 举报

  • TA的每日心情
    慵懒
    2024-10-28 07:07
  • 签到天数: 193 天

    [LV.7]常住居民III

    710

    主题

    5895

    回帖

    6714

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6714

    荣誉开发者喜迎中秋油中2周年生态建设者

    发表于 2024-9-11 09:29:19 | 显示全部楼层
    wuxin0011 发表于 2024-9-11 09:20
    道长还重视算法练习hh

    主要想挑战一下leetcode能不能进一万名
    但是目前遥遥无期
    刚打100道
    差不多进度也就15%吧
    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。
    回复

    使用道具 举报

    该用户从未签到

    0

    主题

    25

    回帖

    20

    积分

    助理工程师

    积分
    20
    发表于 2024-9-13 09:22:41 | 显示全部楼层
    刷题进1w名差不多需要350道
    回复

    使用道具 举报

    发表回复

    本版积分规则

    快速回复 返回顶部 返回列表