当前位置: 首页 > news >正文

[Go版]算法通关村第十四关白银——堆高效解决的经典问题(在数组找第K大的元素、堆排序、合并K个排序链表)

目录

题目:在数组中找第K大的元素

题目链接:LeetCode-215. 数组中的第K个最大元素
在这里插入图片描述

解法1:维护长度为k的最小堆,遍历n-k个元素,逐一和堆顶值对比后,和堆顶交换,最后返回堆顶

复杂度:时间复杂度 O ( k + ( n − k ) l o g k ) O(k+(n-k)logk) O(k+(nk)logk)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func findKthLargest(nums []int, k int) int {length := len(nums)if k > length {return -1}makeMinHeap(nums, k)for i:=k;i<length;i++ {if nums[i] > nums[0] {nums[0], nums[i] = nums[i], nums[0]minHeap(nums, 0, k)}}return nums[0]
}func makeMinHeap(arr []int, length int) {// 从最后一个非叶子节点开始for i:=(length/2-1); i>=0; i-- {minHeap(arr, i, length)}
}// 最小堆化
func minHeap(arr []int, i int, length int) {left, right := 2*i+1, 2*i+2min := iif left < length && arr[left] < arr[min] {min = left}if right < length && arr[right] < arr[min] {min = right}if min != i {arr[i], arr[min] = arr[min], arr[i]minHeap(arr, min, length)}
}

解法2:构建长度为n的最大堆,遍历k次,每次删除堆顶,且堆长度-1,最后返回堆顶(k较小时此法更优)

复杂度:时间复杂度 O ( n + k l o g n ) O(n+klogn) O(n+klogn)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func findKthLargest(nums []int, k int) int {length := len(nums)if k > length {return -1}// 将nums构建为一个最大堆makeMaxHeap(nums, length)for i:=1; i<k; i++ {nums[0], nums[length-i] = nums[length-i], nums[0]maxHeap(nums, 0, length-i)}return nums[0]
}// 最大堆
func makeMaxHeap(arr []int, length int) {// 第一个非叶子节点for i:=(length/2-1); i>=0; i-- {maxHeap(arr, i, length)}
}
// 最大堆化
func maxHeap(arr []int, i int, length int) {l, r, max := 2*i+1, 2*i+2, iif l<length && arr[l] > arr[max] {max = l}if r<length && arr[r] > arr[max] {max = r}if max != i {arr[max], arr[i] = arr[i], arr[max]maxHeap(arr, max, length)}
}

题目:堆排序

题目链接:LeetCode-912. 排序数组
在这里插入图片描述

思路分析:构建长度为n的最大堆,依次删除堆顶并逆序放到数组尾部,且堆长度-1,n-1次后数组则为升序

复杂度:时间复杂度 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

func sortArray(nums []int) []int {length := len(nums)if length == 1 {return nums}makeMaxHeap(nums, length)for i:=length-1; i>0; i-- {nums[0], nums[i] = nums[i], nums[0]maxHeap(nums, 0, i)}return nums
}
// 构建最大堆
func makeMaxHeap(nums []int, length int) {// 第一个非叶子结点for i:=length/2-1; i>=0; i-- {maxHeap(nums, i, length)}
}
// 最大堆化
func maxHeap(nums []int, i int, length int) {l, r, max := 2*i+1, 2*i+2, iif l<length && nums[l] > nums[max] {max = l}if r<length && nums[r] > nums[max] {max = r}if max != i {nums[max], nums[i] = nums[i], nums[max]maxHeap(nums, max, length)}
}

题目:合并K个排序链表

题目链接:LeetCode-23. 合并 K 个升序链表
在这里插入图片描述

思路分析:维护长度为k的最小堆,依次删除堆顶接到返回链表上(纵向拼接),注意取值时判断空链表

复杂度:时间复杂度 O ( k + n l o g k ) O(k+nlogk) O(k+nlogk)、空间复杂度 O ( 1 ) O(1) O(1)

Go代码

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func mergeKLists(lists []*ListNode) *ListNode {length := len(lists)if length == 1 {return lists[0]}// 去除空数组for i:=0; i<length; i++ {if lists[i] == nil {lists[i], lists[length-1] = lists[length-1], lists[i]length--i--}}newList := &ListNode{}tmp := newList// 最小化makeMinHeap(lists, length)for length > 0 && lists[0] != nil {// 取出当前最小tmp.Next = &ListNode{Val:lists[0].Val}tmp = tmp.Nextlists[0] = lists[0].Nextif lists[0] == nil {lists[0], lists[length-1] = lists[length-1], lists[0]length--}if length > 0 && lists[0] != nil {minHeap(lists, 0, length)}}return newList.Next
}func makeMinHeap(arr []*ListNode, length int) {for i:=length/2-1; i>=0; i-- {minHeap(arr, i, length)}
}func minHeap(arr []*ListNode, i, length int) {left, right, min := 2*i+1, 2*i+2, iif left<length && arr[left].Val < arr[min].Val {min = left}if right<length && arr[right].Val < arr[min].Val {min = right}if min != i {arr[min], arr[i] = arr[i], arr[min]minHeap(arr, min, length)}
}

相关文章:

[Go版]算法通关村第十四关白银——堆高效解决的经典问题(在数组找第K大的元素、堆排序、合并K个排序链表)

目录 题目&#xff1a;在数组中找第K大的元素解法1&#xff1a;维护长度为k的最小堆&#xff0c;遍历n-k个元素&#xff0c;逐一和堆顶值对比后&#xff0c;和堆顶交换&#xff0c;最后返回堆顶复杂度&#xff1a;时间复杂度 O ( k ( n − k ) l o g k ) O(k(n-k)logk) O(k(n−…...

『FastGithub』一款.Net开源的稳定可靠Github加速神器,轻松解决GitHub访问难题

&#x1f4e3;读完这篇文章里你能收获到 如何使用FastGithub解决Github无法访问问题了解FastGithub的工作原理 文章目录 一、前言二、项目介绍三、访问加速原理四、FastGithub安装1. 项目下载2. 解压双击运行3. 运行效果4. GitHub访问效果 一、前言 作为开发者&#xff0c;会…...

软件开发的201个原则 阅读笔记 第172-201个原则

目录 原则172 做项目总结 第8章 产品保证原则 原则173 产品保证并不是奢侈品 原则 174 尽早建立软件配置管理过程 原则175 使软件配置管理适应软件过程 原则176 组织SCM 独立于项目管理 原则 177 轮换人员到产品保证组织 给所有中间产品一个名称和版本 原则179 控制基准 原则…...

vue 后台管理系统登录 记住密码 功能(Cookies实现)

安装插件 import Cookies from js-cookie 组件引入 import Cookies from js-cookie; 存值&#xff1a; Cookies.set(username, state.account, { expires: 30 }); // username 存的值的名字&#xff0c;state.account 存的值 expires 存储的时间&#xff0c;30天Cookies…...

elementUI moment 年月日转时间戳 时间限制

changeStartTime(val){debuggerthis.startT val// this.startTime parseInt(val.split(-).join())this.startTime moment(val).unix() * 1000 //开始时间毫秒if(this.endTime){this.endTime moment(this.endT).unix() * 1000 //结束时间毫秒if(this.startTime - this.endTi…...

用AI + Milvus Cloud搭建着装搭配推荐系统教程

以下函数定义了如何将图像转换为向量并插入到 Milvus Cloud 向量数据库中。代码会循环遍历所有图像。(注意:如果需要开启 Milvus Cloud 全新特性动态 Schema,需要修改代码。) 查询向量数据库 以下代码演示了如何使用输入图像查询 Milvus Cloud 向量数据库,以检索和上传…...

大数据领域都有什么发展方向

近年来越来越多的人选择大数据行业&#xff0c;大数据行业前景不错薪资待遇好&#xff0c;各大名企对于大数据人才需求不断上涨。 大数据从业领域很宽广&#xff0c;不管是科技领域还是食品产业&#xff0c;零售业等都是需要大数据人才进行大数据的处理&#xff0c;以提供更好…...

NSSCTF——Web题目1

目录 一、[LitCTF 2023]PHP是世界上最好的语言&#xff01;&#xff01; 二、[LitCTF 2023]Ping 三、[SWPUCTF 2021 新生赛]easyupload1.0 四、[SWPUCTF 2021 新生赛]easyupload2.0 五、[SWPUCTF 2021 新生赛]caidao 一、[LitCTF 2023]PHP是世界上最好的语言&#xff01;&a…...

VScode中写Verilog时,iverilog语法自动纠错功能不起作用

VScode中编写Verilog时&#xff0c;iverilog语法自动纠错功能不起作用 问题&#xff1a;按照教程搭建vscode下Verilog编译环境&#xff0c;发现语法纠错功能一直无效&#xff0c;检查了扩展Verilog-HDL/SystemVerilog/Bluespec SystemVerilog的配置也没有任何问题。 错误原因&a…...

thinkphp6.0 配合shell 脚本 定时任务

1. 执行命令&#xff0c;生成自定义命令 php think make:command Custom<?php declare (strict_types 1);namespace app\command;use app\facade\AdmUser; use think\console\Command; use think\console\Input; use think\console\input\Argument; use think\console\i…...

18-使用钩子函数判断用户登录权限-登录前缀

钩子函数的两种应用: (1). 应用在app上 before_first_request before_request after_request teardown_request (2). 应用在蓝图上 before_app_first_request #只会在第一次请求执行,往后就不执行, (待定,此属性没调试通过) before_app_request # 每次请求都会执行一次(重点…...

关闭win11启动界面搜索推荐

环境&#xff1a;win11 最近win11更新了某些功能&#xff0c;附带加上了搜索推荐的功能。对于启动菜单的搜索功能&#xff0c;我只想搜索我自己的安装的程序&#xff0c;快速打开&#xff0c;不希望看到搜索推荐&#xff0c;更不希望多点击一下&#xff0c;偶尔还会打开浏览器看…...

中文乱码处理

&#x1f600;前言 中文乱码处理 &#x1f3e0;个人主页&#xff1a;尘觉主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是尘觉&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力&#x1f609;&#x1f609; 在csdn获奖荣誉: &#x1f3c…...

JAVA坦克大战游戏v3

JAVA坦克大战游戏v3 素材 bomb_3.gif bomb_2.gif bomb_1.gif 项目结构 游戏演示 MyTankGame3.java /*** 功能:坦克游戏的5.0[]* 1.画出坦克.* 2.我的坦克可以上下左右移动* 3.可以发射子弹,子弹连发(最多5)* 4.当我的坦克击中敌人坦克时&#xff0c;敌人就消失(爆炸的效…...

使用acme,自动续签免费的SSL,无忧http升级https

使用acme自动续签免费的SSL 安装acme.sh颁发域名将证书安装到nginx下配置nginx的ssl自动续签 这里只进行最简单的操作 安装acme.sh 进入你的用户目录&#xff0c;如果你使用root登陆&#xff0c;那么你的用户目录就是 /root/ curl https://get.acme.sh | sh -s emailmyexam…...

Uniapp笔记(五)uniapp语法4

本章目标 授权登录【难点、重点】 条件编译【理解】 小程序分包【理解】 一、授权登录 我的模块其实是两个组件&#xff0c;一个是登录组件&#xff0c;一个是用户信息组件&#xff0c;根据用户的登录状态判断是否要显示那个组件 1、登录的基本布局 <template><…...

编写一个yolov5的模型检测,只要运行后,就不结束,只要有文件放入到文件夹中,就去执行读取

编写一个yolov5的模型检测&#xff0c;只要运行后&#xff0c;就不结束&#xff0c;只要有文件放入到文件夹中&#xff0c;就去执行读取 import os import cv2 import torch from torchvision import transforms from PIL import Image from yolo.model import YOLO…...

vscode调试PHP代码

目录 准备工作ssh的连接以及配置调试 准备工作 1.首先你需要下载一个vscode 2.下载模块 你需要在VScode中去下载我们所需的两个模块PHP Debug以及remote -ssh 3.安装对应版本的xdebug 需要在xdebug的官方去进行分析&#xff0c;选择适合你自己版本的xdebug 去往官方&#x…...

js reverse实现数据的倒序

2023.8.25今天我学习了如何在数组顺序进行倒序排列&#xff0c;如&#xff1a; 原数组为&#xff1a; 我们只需要对数组使用reverse()方法 let demo [{id: 1, name: 一号},{id: 2, name: 二号},{id: 3, name: 三号},]demo.reverse()console.log(demo) 扩展&#xff1a; 当我…...

日常踩坑记录

本篇文章主要介绍一下最近的开发中用到的些小问题。问题不大&#xff0c;但有些小细节&#xff0c;记录一下&#xff0c;有遇到的朋友可以看一下&#xff0c;有更好的解决方法欢迎分享。 浏览器记住密码自动填充表单 这个问题我在火狐浏览器遇到了。我登录系统时选择了浏览器…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...

Linux信号保存与处理机制详解

Linux信号的保存与处理涉及多个关键机制&#xff0c;以下是详细的总结&#xff1a; 1. 信号的保存 进程描述符&#xff08;task_struct&#xff09;&#xff1a;每个进程的PCB中包含信号相关信息。 pending信号集&#xff1a;记录已到达但未处理的信号&#xff08;未决信号&a…...