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

【LeetCode】每日一题 2024_6_4 将元素分配到两个数组中 II(二分、离散化、树状数组)

文章目录

  • LeetCode?启动!!!
  • 题目:将元素分配到两个数组中 II
    • 题目描述
    • 代码与解题思路
  • 每天进步一点点

LeetCode?启动!!!

在这里插入图片描述
又有段时间没写每日一题的分享了,原本今天是打算早上发完晨起计划之后发的,但是今天太忙了,忙着忙着一直没时间把文章写完,拖着拖着就拖到晚上了

只能在晚上离散数学的课上悄摸摸写完发了

题目:将元素分配到两个数组中 II

题目链接:将元素分配到两个数组中 II

题目描述

代码与解题思路

// 树状数组
type fenwick []int// 维护 [1, i] 的元素个数
func (f fenwick) add(i int) {for ; i < len(f); i += i & -i {f[i]++}
}// 获取 [1, i] 的元素个数和
func (f fenwick) pre(i int) (res int) {for ; i > 0; i &= i - 1 {res += f[i]}return res
}func resultArray(nums []int) []int {// 排序去重 -> 离散化sorted := slices.Clone(nums)slices.Sort(sorted)sorted = slices.Compact(sorted)m := len(sorted)a, b := []int{nums[0]}, []int{nums[1]}// 维护树状数组t1, t2 := make(fenwick, m+1), make(fenwick, m+1)for i, v := range sorted {if v == nums[0] {t1.add(i+1)} if v == nums[1] {t2.add(i+1)}}for _, x := range nums[2:] {// 二分查找离散化数组的下标位置l, r := 0, len(sorted)for l < r {mid := (l+r)>>1if sorted[mid] < x {l = mid+1} else {r = mid}}v := l+1// greaterCount: 用数组所有元素 - 小于等于 val 元素的数量 = 大于 val 元素的数量gc1 := len(a) - t1.pre(v)gc2 := len(b) - t2.pre(v)if gc1 > gc2 || gc1 == gc2 && len(a) <= len(b) {a = append(a, x)t1.add(v)} else {b = append(b, x)t2.add(v)}}return append(a, b...)
}

代码的核心思路比较短,题目比较好理解(看着像是一个简单的模拟题)但是他给到的数据范围是 10^5,也就是他没法用暴力的算法去做

根据题目需要维护大于某个数的元素个数的要求,以及 10^9 次方的数字大小,我们可以用离散化 + 维护树状数组解决

两个问题

1)如何离散化?

sorted := slices.Clone(nums)
slices.Sort(sorted)
sorted = slices.Compact(sorted)

排序去重好的 sorted 数组,假设是 [ 7, 12, 23, 40 ],我们在 nums 数组找到 23 这个元素的时候,就能根据这个元素在 sorted 数组中的位置,求的有 2 个数比他小,1 个数比他大

这就是离散化的意义

2)树状数组?

// 树状数组
type fenwick []int// 维护 [1, i] 的元素个数
func (f fenwick) add(i int) {for ; i < len(f); i += i & -i {f[i]++}
}// 获取 [1, i] 的元素个数和
func (f fenwick) pre(i int) (res int) {for ; i > 0; i &= i - 1 {res += f[i]}return res
}

关于上述代码的解释:(对于树状数组的简单解释)

为什么用树状数组?因为树状数组能够 logN 获取一个区间的前缀和,并能够 logN 的复杂度修改区间的值。

树状数组中,通过不断加上 lowbit 可以获得每个关键区间,让 [1, i] 区间增加或减少一个值(add 操作)

而通过不断减去 lowbit 可以获得区间和 [1, i](pre 操作)

求 lowbit 的方法:i & -i

减去 lowbit 的方法:i &= i-1

什么是 lowbit?

=> 10010 中,10 就是 lowbit

每天进步一点点

可以和我刷一辈子的每日一题吗?
一题一题,积累起来就是一辈子。

相关文章:

【LeetCode】每日一题 2024_6_4 将元素分配到两个数组中 II(二分、离散化、树状数组)

文章目录 LeetCode&#xff1f;启动&#xff01;&#xff01;&#xff01;题目&#xff1a;将元素分配到两个数组中 II题目描述代码与解题思路 每天进步一点点 LeetCode&#xff1f;启动&#xff01;&#xff01;&#xff01; 又有段时间没写每日一题的分享了&#xff0c;原本今…...

JAVA小案例-break练习,随机数,到88停止

JAVA小案例-break练习&#xff0c;随机数&#xff0c;到88停止 代码如下&#xff1a; public class Break {/*** break练习&#xff0c;随机数&#xff0c;到88停止* param args*/public static void main(String[] args) {int count0;//计数器System.out.println("Begi…...

C++第三方库【httplib】断点续传

什么是断点续传 上图是我们平时在浏览器下载文件的场景&#xff0c;下载的本质是数据的传输。当出现网络异常&#xff0c;浏览器异常&#xff0c;或者文件源的服务器异常&#xff0c;下载都可能会终止。而当异常解除后&#xff0c;重新下载文件&#xff0c;我们希望从上一次下载…...

[SaaS] AI+数据,tiktok选品,找达人,看广告数据

TK观察专访丨前阿里“鲁班”创始人用AIGC赋能TikTok获千万融资用AI数据做TikTokhttps://mp.weixin.qq.com/s/xp5UM3ROo48DK4jS9UBMuQ主要还是爬虫做数据的。 商家做内容&#xff1a;1.找达人拍内容&#xff0c;2.商家自己做原生自制内容&#xff0c;3.广告内容。 短视频&…...

A股冲高回落,金属、地产板块领跌,新股N汇成真首日暴涨753%

行情概述 AH股有色金属、教育及地产板块领跌&#xff0c;军工航天及半导体板块逆势走强&#xff1b;锂电池、创新药概念股也走强。创业板新股N汇成真首日暴涨753%&#xff0c;触发二次临停。 周三A股冲高回落&#xff0c;上证指数收跌0.83%&#xff0c;深成指跌0.8%&#xff…...

dns域名解析服务和bond网卡

目录 dns域名解析服务 一、DNS 1、定义 2、以www.baidu.com为例 3、域名体系结构 4、DNS解析使用的协议和端口 5、dns域名解析的过程 6、dns解析的优先级 二、如何实现域名解析 1、域名解析 2、bind配置文件位置 &#xff08;一&#xff09;正向解析 &#xff08;…...

视频生成框架EasyAnimate正式开源!

近期&#xff0c;Sora模型的热度持续上涨&#xff0c;社区中涌现了一些类Sora的开源项目&#xff0c;这些项目均基于Diffusion Transformer结构&#xff0c;使用Transformer结构取代了UNet作为扩散模型的基线&#xff0c;旨在生成更长、更高分辨率、且效果更好的视频。EasyAnim…...

【微机原理与汇编语言】并行接口8255实验

一、实验目的 掌握可编程并行接口芯片8255的工作原理及初始化方法掌握8255在实际应用中的硬件连接及编程应用 二、实验要求 根据实验室现有条件&#xff0c;针对实验任务&#xff0c;设计实验方案并进行实现。 三、实验内容 启动0#计数器&#xff0c;每计5个数&#xff08…...

Oracle表分区的基本使用

什么是表空间 是一个或多个数据文件的集合&#xff0c;所有的数据对象都存放在指定的表空间中&#xff0c;但主要存放的是表&#xff0c;所以称为表空间 什么是表分区 表分区就是把一张大数据的表&#xff0c;根据分区策略进行分区&#xff0c;分区设置完成之后&#xff0c;…...

6月5号作业

设计一个Per类&#xff0c;类中包含私有成员:姓名、年龄、指针成员身高、体重&#xff0c;再设计一个Stu类&#xff0c;类中包含私有成员:成绩、Per类对象p1&#xff0c;设计这两个类的构造函数、析构函数 ​ #include <iostream>using namespace std; class Slu { priv…...

中继器、集线器、网桥、交换机、路由器和网关

目录 前言一、中继器、集线器1.1 中继器1.2 集线器 二、网桥、交换机2.1 网桥2.1.1 认识网桥2.1.2 网桥的工作原理2.1.3 生成树网桥 2.2 交换机2.2.1 交换机的特征2.2.2 交换机的交换模式2.2.3 交换机的功能 三、路由器、网关3.1 路由器的介绍3.2 路由器的工作过程3.2.1 前置知…...

揭秘相似矩阵:机器学习算法中的隐形“纽带”

在机器学习领域&#xff0c;数据的处理和分析至关重要。如何有效地从复杂的数据集中提取有价值的信息&#xff0c;是每一个机器学习研究者都在努力探索的问题。相似矩阵&#xff0c;作为衡量数据之间相似性的数学工具&#xff0c;在机器学习算法中扮演着不可或缺的角色。 相似矩…...

攻防世界—webbaby详解

1.ssrf注入漏洞 ssrf&#xff08;服务端请求伪造&#xff09;是一种安全漏洞&#xff0c;攻击者通过该漏洞向受害服务器发出伪造的请求&#xff0c;从而访问并获取服务器上的资源&#xff0c;常见的ssrf攻击场景包括访问内部网络的服务&#xff0c;执行本地文件系统命令&#…...

MySQL中:cmd下输入命令mysql -uroot -p 连接数据库错误

目录 问题cmd下输入命令mysql -uroot -p错误 待续、更新中 问题 cmd下输入命令mysql -uroot -p错误 解决 配置环境变量&#xff1a;高级系统设置——环境变量——系统变量——path编辑——新建——MySQL.exe文件路径&#xff08;如下图所示&#xff09; phpstudy2018软件下&am…...

【开发利器】使用OpenCV算子工作流高效开发

学习《人工智能应用软件开发》&#xff0c;学会所有OpenCV技能就这么简单&#xff01; 做真正的OpenCV开发者&#xff0c;从入门到入职&#xff0c;一步到位&#xff01; OpenCV实验大师Python SDK 基于OpenCV实验大师v1.02版本提供的Python SDK 实现工作流导出与第三方应用集…...

基础数学-求平方根(easy)

一、问题描述 二、实现思路 1.题目不能直接调用Math.sqrt(x) 2.这个题目可以使用二分法来缩小返回值范围 所以我们在left<right时 使 mid (leftright)/21 当mid*mid>x时&#xff0c;说明right范围过大&#xff0c;rightright-1 当mid*mid<x时&#xff0c;说明left范…...

c语言项目-贪吃蛇项目2-游戏的设计与分析

文章目录 前言游戏的设计与分析地图&#xff1a;这里简述一下c语言的国际化特性相关的知识<locale.h> 本地化头文件类项setlocale函数 上面我们讲到需要打印★&#xff0c;●&#xff0c;□三个宽字符找到这三个字符打印的方式有两种&#xff1a; 控制台屏幕的长宽特性&a…...

力扣2831.找出最长等值子数组

力扣2831.找出最长等值子数组 思路&#xff1a;用二维数组存每个数字的出现下标 遍历所有数字求结果当前子数组大小&#xff1a;pos[i] - pos[j] 1;当前相同数个数&#xff1a;i - j 1;需要删去的数的个数&#xff1a;pos[i] - pos[j] - i j; class Solution {public:int…...

17K star,一款开源免费的手机电脑无缝同屏软件

导读&#xff1a;白茶清欢无别事&#xff0c;我在等风也等你。 作为程序员&#xff0c;在我们的工作中经常需要把手机投票到电脑进行调试工作&#xff0c;选择一款功能强大的投屏软件是一件很必要的事情。今天给大家介绍一款开源且免费的投屏软件&#xff0c;极限投屏&#xff…...

正则表达式二

修饰符 i&#xff1a;将匹配设置为不区分大小写&#xff0c;即A和a没有区别 var str"Google Runoob taobao runoob"; var n1str.match(/runoob/g); //runoob var n2str.match(/runoob/gi); //Runoob&#xff0c;runoobg&#xff1a;重找所有匹配项&#xff0…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...