LeeCode912. 排序数组
给你一个整数数组 nums
,请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n))
,并且空间复杂度尽可能小。
示例 1:
输入:nums = [5,2,3,1] 输出:[1,2,3,5]
示例 2:
输入:nums = [5,1,1,2,0,0] 输出:[0,0,1,1,2,5]
提示:
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
代码:
#include "solution.h"
#include <algorithm>
#include <vector>
#include <set>
#include <stdlib.h>static void swapeValue(int& a, int& b) {int temp = a;a = b;b = temp;
}static int getMiddleVal(int a, int b, int c) {int arr[] = {a, b, c};// 等号右边是lambda表达式,表示一个匿名函数,参数是俩个指针,返回int值。 符号 ->int 可省略,能自动推导出返回值类型auto compareFuc = [](const void* p1, const void* p2) ->int {return *((int*)p1) - *((int*)p2);};// 这里c语言的qsort函数,只排序a,b,c 3个数。这里偷个懒了qsort(arr, sizeof(arr) / sizeof(arr[0]), sizeof(arr[0]), compareFuc);return arr[1];
}// 将数组这个区间分成左右两个区间,返回中间数的idx,左边区间的所有数小于idx索引处的数,右边区间的数都大于idx索引处的数
// 为了找到这个idx,过程中可以交换一些数的值。
static int getIdx(vector<int>& nums, int startIdx, int endIdx) { static auto flag = true; // 有很多相同数字时,超时!为解决这个问题,引入变量flag,让中间值尽量处在区域中间的某个位置if (startIdx == endIdx - 1) {// 相邻的if (nums[endIdx] < nums[startIdx]) {int temp = nums[startIdx];nums[startIdx] = nums[endIdx];nums[endIdx] = temp;}return startIdx;}// 尽量用区域中间某个值作为分界线int idx = startIdx;int midIdx = (startIdx + endIdx) >> 1;int middleVal = getMiddleVal(nums[startIdx], nums[midIdx], nums[endIdx]);int idx_ = startIdx; // 中间那个值对应的索引if (nums[midIdx] == middleVal) {idx_ = midIdx;}else if (nums[endIdx] == middleVal) {idx_ = endIdx;}if (idx_ != idx) {swapeValue(nums[idx], nums[idx_]);}for (int i = startIdx + 1; i <= endIdx; i++) {if (nums[i] < nums[idx] || (flag && nums[i] == nums[idx])) {// 交换nums[i]和 nums[idx + 1]的值// 交换nums[idx] 和nums[idx + 1]的值。// idx值+1// 这样,那个小的值就交换到前面了swapeValue(nums[i], nums[idx + 1]);swapeValue(nums[idx], nums[idx + 1]);++idx;flag = !flag;}}return idx;
}void qsort(vector<int>& nums, int startIdx, int endIdx) {if (startIdx >= endIdx)return;int idx = getIdx(nums, startIdx, endIdx);qsort(nums, startIdx, idx - 1);qsort(nums, idx + 1, endIdx);
}class Solution {
public:vector<int> sortArray(vector<int>& nums) {if (nums.size() < 2) {return nums;}qsort(nums, 0, nums.size() - 1);return nums;}
};
测试代码:
void testLeeCode912() { // 排序数组vector<int> nums = {5, 2, 3, 1};Solution* solution = new Solution();solution->sortArray(nums);for (auto& val : nums) {std::cout << val << endl;}delete solution; // 回收内存
}
测试结果:
ok!
提交到LeeCode:
ok!
总结:总体方法是分段排序。需要将数组分为俩个区域,有中间的一个数,左边的数都小于这个数,右边的数都大于这个数,再对递归每个区域用同样方法。 但是特殊情况容易超时,比如数组是倒序的,或者数组多数数字都一样的情况,这俩种递归次数太多,然后一步步优化。
相关文章:
LeeCode912. 排序数组
给你一个整数数组 nums,请你将该数组升序排列。 你必须在 不使用任何内置函数 的情况下解决问题,时间复杂度为 O(nlog(n)),并且空间复杂度尽可能小。 示例 1: 输入:nums [5,2,3,1] 输出:[1,2,3,5]示例 2…...
Maven 简介(图文)
Maven 简介 Maven 是一个Java 项目管理和构建的工具。可以定义项目结构、项目依赖,并使用统一的方式进行自动化构建,是Java 项目不可缺少的工具。 Maven 的作用 提供标准化的项目结构:以前不同的开发工具创建的项目结构是不一样的…...
深入规划 Elasticsearch 索引:策略与实践
一、Elasticsearch 索引概述 (一)索引基本概念 Elasticsearch 是一个分布式、高性能的全文搜索引擎,其核心概念之一便是索引。索引本质上是一个存储文档的逻辑容器,它使得数据能够在高效的检索机制下被查询到。当我们对文档进行…...
基于X86/RK/全志+FPGA+AI工业一体机在电力接地系统中的应用方案
随着电力技术的发展和需求增加,智能电网建设受到全球关注。电力五防系统建设是确保我国电力安全的核心任务,接地管理系统是其中的关键部分,对电力系统的安全、稳定和高效运行至关重要。工业一体机,凭借其卓越的性能、稳定性和环境…...
论文阅读:2024 arxiv AI Safety in Generative AI Large Language Models: A Survey
总目录 大模型安全相关研究:https://blog.csdn.net/WhiffeYF/article/details/142132328 AI Safety in Generative AI Large Language Models: A Survey https://arxiv.org/pdf/2407.18369 https://www.doubao.com/chat/3262156521106434 速览 研究动机&#x…...
JVM对象创建全过程
JVM对象创建全过程深度解析 1. 对象创建的整体流程 JVM创建对象的过程可以分为7个关键步骤,从类检查到内存分配,再到对象初始化: 类加载检查 → 内存分配 → 内存空间初始化 → 对象头设置 → 构造函数执行 → 栈帧引用建立 → 对象使用2.…...
ubuntu 22.04 使用ssh-keygen创建ssh互信账户
现有两台ubuntu 22.04服务器,ip分别为192.168.66.88和192.168.88.66。需要将两台服务器创建新用户并将新用户做互信。 创建账户 adduser user1 # 如果此用户不想使用密码,直接一直回车就行,创建的用户是没法使用用户密码进行登陆的 su - …...
蓝牙开发那些事儿12——(记一颗BLE芯片BringUp折腾过程)
1.背景 蓝牙这个系列已经很久很久没有更新了,感慨良多。 现在写这篇文章主要是BringUp一颗蓝牙芯片的过程中遇到了一些奇怪的问题,想了一些办法,一一克服了,看看对其他做蓝牙的同学有没有启发。 同时也安利一个叫做HACKRF的设备…...
从零构建 Vue3 登录页:结合 Vant 组件与 Axios 实现完整登录功能
在 Web 开发的世界里,登录页是用户与应用交互的第一道门槛,它的体验好坏直接影响着用户对整个应用的印象。本文将详细记录如何使用 Vue3、Vant 组件库和 Axios 构建一个兼具美观与实用的登录页面,并实现完整的登录逻辑与数据验证,…...
AutoSAR从概念到实践系列之MCAL篇(一)——MCAL架构及其模块详解
欢迎大家学习我的《AutoSAR从概念到实践系列之MCAL篇》系列课程,我是分享人M哥,目前从事车载控制器的软件开发及测试工作。 学习过程中如有任何疑问,可底下评论! 如果觉得文章内容在工作学习中有帮助到你,麻烦点赞收藏评论+关注走一波!感谢各位的支持! 老规矩,…...
多线程编程的简单案例——单例模式[多线程编程篇(3)]
目录 前言 1.wati() 和 notify() wait() 和 notify() 的产生原因 如何使用wait()和notify()? 案例一:单例模式 饿汉式写法: 懒汉式写法 对于它的优化 再次优化 结尾 前言 如何简单的去使用jconsloe 查看线程 (多线程编程篇1)_eclipse查看线程-CSDN博客 浅谈Thread类…...
万物互联时代,AWS IoT Core如何构建企业级物联网中枢平台?
在智能制造、智慧城市、车联网等场景爆发的今天,全球物联网设备数量已突破150亿台。企业如何高效管理海量设备并挖掘数据价值?AWS IoT Core作为亚马逊云科技推出的全托管物联网平台,正在为数千家企业提供设备连接、数据采集、实时分析的一站式…...
论文阅读:2023 arxiv Safe RLHF: Safe Reinforcement Learning from Human Feedback
总目录 大模型安全相关研究:https://blog.csdn.net/WhiffeYF/article/details/142132328 Safe RLHF: Safe Reinforcement Learning from Human Feedback https://arxiv.org/pdf/2310.12773 https://github.com/PKU-Alignment/safe-rlhf 速览 研究动机ÿ…...
链表相关算法题
小细节 初始化问题 我们这样子new一个ListNode 它里面的默认值是0,所以我们不能这样 如果我们为空,我们要返回null 节点结束条件判断(多创建节点问题) 参考示例3217 解析: 我的答案是多了一个无用节点 这是因为我每…...
招商信诺原点安全:一体化数据安全管理解决方案荣获“鑫智奖”!
近日,“鑫智奖 2025第七届金融数据智能优秀解决方案评选”榜单发布,原点安全申报的《招商信诺:数据安全一体化管理解决方案》荣获「信息安全创新优秀解决方案」。 “鑫智奖第七届金融数据智能优秀解决方案评选”活动由金科创新社主办&#x…...
实战篇|多总线网关搭建与量产验证(5000 字深度指南)
引言 1. 环境准备与硬件选型 1.1 项目需求分析 1.2 SoC 与开发板选型 1.3 物理接口与 PCB 设计 1.4 电源与供电保护 2. 软件架构与协议栈移植 2.1 分层架构详解 2.2 协议栈移植步骤 2.3 高可用驱动设计 2.4 映射逻辑与 API 定义 3. 开发流程与实践 3.1 敏捷迭代与里程碑 3.2 核…...
Jenkins 简易使用记录
一、Jenkins 核心功能与适用场景 核心功能: 持续集成(CI):自动构建代码、运行单元测试。持续交付(CD):自动化部署到测试/生产环境。任务调度:定时执行任务(如备份、清理&…...
第十四节:实战场景-何实现全局状态管理?
React.createElement调用示例 Babel插件对JSX的转换逻辑 React 全局状态管理实战与 JSX 转换原理深度解析 一、React 全局状态管理实现方案 1. Context API useReducer 方案(轻量级首选) // 创建全局 Context 对象 const GlobalContext createConte…...
启动vite项目报Unexpected “\x88“ in JSON
启动vite项目报Unexpected “\x88” in JSON 通常是文件被防火墙加密需要寻找运维解决 重启重装npm install...
Jenkins 多分支管道
如果您正在寻找一个基于拉取请求或分支的自动化 Jenkins 持续集成和交付 (CI/CD) 流水线,本指南将帮助您全面了解如何使用 Jenkins 多分支流水线实现它。 Jenkins 的多分支流水线是设计 CI/CD 工作流的最佳方式之一,因为它完全基于 git(源代…...
PHP腾讯云人脸核身获取NONCE ticket
参考腾讯云官方文档: 人脸核身 获取 NONCE ticket_腾讯云 前提条件,已经成功获取了access token。 获取参考文档: PHP腾讯云人脸核身获取Access Token-CSDN博客 public function getTxFaceNonceTicket($uid) {$access_token file_get_c…...
云计算(Cloud Computing)概述——从AWS开始
李升伟 编译 无需正式介绍亚马逊网络服务(Amazon Web Services,简称AWS)。作为行业领先的云服务提供商,AWS为全球开发者提供了超过170项随时可用的服务。 例如,Adobe能够独立于IT团队开发和更新软件。通过AWS的服务&…...
51单片机实验五:A/D和D/A转换
一、实验环境与实验器材 环境:Keli,STC-ISP烧写软件,Proteus. 器材:TX-1C单片机(STC89C52RC)、电脑。 二、 实验内容及实验步骤 1.A/D转换 概念:模数转换是将连续的模拟信号转换为离散的数字信…...
重构未来智能:Anthropic 解码Agent设计哲学三重奏
第一章 智能体进化论:从工具到自主体的认知跃迁 1.1 LLM应用范式演进图谱 阶段技术形态应用特征代表场景初级阶段单功能模型硬编码规则执行文本摘要/分类进阶阶段工作流编排多模型协同调度跨语言翻译流水线高级阶段自主智能体动态决策交互编程调试/客服对话 1.1.…...
MCP协议在纳米材料领域的深度应用:从跨尺度协同到智能研发范式重构
MCP协议在纳米材料领域的深度应用:从跨尺度协同到智能研发范式重构 文章目录 MCP协议在纳米材料领域的深度应用:从跨尺度协同到智能研发范式重构一、MCP协议的技术演进与纳米材料研究的适配性分析1.1 MCP协议的核心架构升级1.2 纳米材料研发的核心挑战与…...
.NET Core 服务实现监控可观测性最佳实践
.NET Core 概述 .Net Core 是一个开源的、跨平台的高性能框架,由微软开发并维护,现由 .NET Foundation 提供支持。它用于构建现代化、可扩展的云端和本地应用程序,支持开发 Web 应用、微服务、API、物联网应用以及移动后端服务,是…...
ios精灵脚本辅助软件,有根和无根roothide越狱区别
最新版本的ios按键精灵app 支持到15-16系统,可以在半越狱环境下和无根越狱环境安装,对于很多用户一直不理解有根和无根之间的差别,今天简单介绍下 最高权限和部分权限的区别 1、有根越狱 – 有系统根目录读写权限(通过越狱软件可…...
ChatGPT-o3辅助学术大纲效果如何?
目录 1 引言 2 背景综述 2.1 自动驾驶雷达感知 2.2 生成模型演进:从 GAN 到 Diffusion 3 相关工作 3.1 雷达点云增强与超分辨率 3.2 扩散模型在数据增广中的应用 4 方法论 4.1 问题定义与总览 4.2 数据预处理与雷达→体素表示 4.3 潜在体素扩散网络&…...
PyCharm 2024.3.5 状态栏添加前进后退按钮
操作路径:Appearance & Behavior -> Menu and Toolbars -> Main Toolbar -> Left -> Add… 按钮位置:Main Menu -> Navigate -> OK 最终效果...
【CPP】死锁产生、排查、避免
一、死锁产生 死锁是指两个或多个线程互相等待对方释放资源,导致程序无法继续执行的现象。在多线程编程中,死锁是一种常见且严重的并发问题。死锁产生必须要四个条件同时满足才会发生: 互斥条件:某些资源只能由一个线程占用。占…...
深入理解 Android Handler
一、引言 Handler 在安卓中的地位是不言而喻的,几乎维系着整个安卓程序运行的生命周期,但是这么重要的一个东西,我们真的了解它吗?下面跟随着我的脚步,慢慢揭开Hanler的神秘面纱吧! 本文将介绍Handler 的运…...
Git 进阶之路:高效协作之分支管理
🌈 个人主页:Zfox_ 🔥 系列专栏:Git 企业级应用 目录 一:🔥 分⽀管理 🦋 理解分⽀🦋 创建分⽀🦋 切换分⽀🦋 合并分⽀🦋 删除分⽀🦋 合…...
LeetCode 2364.统计坏数对的数目:反向统计
【LetMeFly】2364.统计坏数对的数目:反向统计 力扣题目链接:https://leetcode.cn/problems/count-number-of-bad-pairs/ 给你一个下标从 0 开始的整数数组 nums 。如果 i < j 且 j - i ! nums[j] - nums[i] ,那么我们称 (i, j) 是一个 坏…...
6.Rust+Axum:打造高效 WebSocket 实时通信聊天室
摘要 本文详细介绍 RustAxum 在 WebSocket 实时通信开发中的应用,包括双向通信、状态管理等,实践构建聊天室应用。 一、引言 在当今的 Web 应用开发中,实时通信变得越来越重要。WebSocket 作为一种在单个 TCP 连接上进行全双工通信的协议&…...
【硬件系统架构】冯·诺依曼架构
一、引言 在计算机科学的广袤领域中,冯诺依曼架构犹如一颗璀璨的恒星,照亮了现代计算机发展的道路。从我们日常使用的个人电脑到强大的数据中心服务器,几乎都基于这一架构构建。它的出现是计算机发展史上的一个重要里程碑,深刻地影…...
Android 13 关闭屏幕调节音量大小
一、问题描述 在Android 13系统中,通过修改frameworks/base/core/res/res/values/config.xml配置文件,实现灭屏状态下调节音量的功能。 二、修改内容 diff --git a/frameworks/base/core/res/res/values/config.xml b/frameworks/base/core/res/res/values/config.xml inde…...
[编程基础] Java · 学习手册
🔥 《Java 工程师修炼之路:从零构建系统化知识体系》 🔥 🛠️ 专栏简介: 这是一个以工业级开发标准打造的 Java 全栈技术专栏,涵盖语言核心、并发编程、JVM 原理、框架源码、架构设计等全维度知识体系。专…...
探索元生代:ComfyUI 工作流与计算机视觉的奇妙邂逅
目录 一、引言 二、蓝耘元生代和 ComfyUI 工作流初印象 (一)蓝耘元生代平台简介 (二)ComfyUI 工作流创建是啥玩意儿 三、计算机视觉是个啥 (一)计算机视觉的基本概念 (二)计算…...
C++ 迭代器失效详解:如何避免 vector 操作中的陷阱
目录 1. 什么是迭代器失效? 2. 哪些操作会导致迭代器失效? 2.1 vector 的插入操作(push_back, insert) 示例:push_back 导致迭代器失效 如何避免? 2.2 vector 的删除操作(erase, pop_back&…...
【fisco bcos】基于ABI调用智能合约
参考官方文档:https://fisco-bcos-documentation.readthedocs.io/zh-cn/latest/docs/sdk/java_sdk/assemble_transaction.html 先放一下智能合约: (就是一个很简单的插入和查找嗯) pragma solidity ^0.4.25; pragma experimental…...
【Python学习笔记】Pandas实现Excel质检记录表初审、复核及质检统计
背景: 我有这样一个需要审核的飞书题目表,按日期分成多个sheet,有初审——复核——质检三个环节,这三个环节是不同的同学在作业,并且领到同一个题目的人选是随机的,也就是说,完成一道题的三个人…...
Springboot 自动装配原理是什么?SPI 原理又是什么?
1. Spring Boot 自动装配原理 自动装配是 Spring Boot 简化配置的核心机制,其核心思想是根据类路径中的依赖自动配置 Spring 应用。 关键步骤: 启动注解 SpringBootApplication 该注解组合了 EnableAutoConfiguration,用于激活自动配置。 …...
【英语语法】基本句型
目录 前言一:主谓二:主谓宾三:主系表四:主谓双宾五:主谓宾补 前言 英语基本句型是语法体系的基石,以下是英语五大基本句型。 一:主谓 结构:主语 不及物动词 例句: T…...
扫雷-C语言版
C语言扫雷游戏设计(完整版) 游戏背景 扫雷是一款经典的益智类单人电脑游戏,最早出现在1960年代,并在1990年代随着Windows操作系统而广为人知。游戏目标是在不触发任何地雷的情况下,揭开所有非地雷的格子。玩家需要根…...
【C++初阶】--- list容器功能模拟实现
1.什么是list容器 在 C 标准模板库(STL)中,std::list 是一个非常有用的容器,它是双向链表的实现std::list 是一种序列式容器,它允许在序列内的任意位置进行高效的插入和删除操作。与数组和 std::vector 不同ÿ…...
gRPC 介绍及在嵌入式 Linux 下的成功编译及使用详解
gRPC 是一个高性能、开源和通用的 RPC 框架,由 Google 开发。它支持多种编程语言,并且能够运行在不同的环境中,包括嵌入式系统。本文将详细介绍 gRPC,以及如何在嵌入式 Linux 系统下成功编译 gRPC,并结合 protobuf 和 …...
C语言教程(十):C 语言函数详解
一、引言 在 C 语言中,函数是一组执行特定任务的代码块。通过将复杂的程序逻辑划分为多个函数,不仅能提高代码的可读性、可维护性,还便于代码的复用。无论是简单的数学计算,还是复杂的系统操作,函数都发挥着核心作用。…...
力扣刷题-热题100题-第35题(c++、python)
146. LRU 缓存 - 力扣(LeetCode)https://leetcode.cn/problems/lru-cache/?envTypestudy-plan-v2&envIdtop-100-liked 双向链表哈希表 内置函数 对于c有list可以充当双向链表,unordered_map充当哈希表;python有OrderedDic…...
LeetCode算法题(Go语言实现)_52
题目 给你一个下标从 0 开始的整数数组 costs ,其中 costs[i] 是雇佣第 i 位工人的代价。 同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人: 总共进行 k 轮雇佣,且每一轮恰好雇佣一位工人。 在每一轮雇佣中…...
基于尚硅谷FreeRTOS视频笔记——13—HAL库和RTOS时钟源问题
RTOS的时钟源就是系统定时器中断,通俗来说就是系统定时器每中断一次,就扫描一次RTOS,查看RTOS中有没有任务的切换。 但是,系统存在一个HAL_Delay()函数,就是使用的系统定时器中断来执行的函数。 当我们在RTOS中&…...