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

leetcode 912. 排序数组

912. 排序数组

  • 912. 排序数组

题目

给你一个整数数组 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

题解

  • 接收一个数组 nums,通过计数排序的方法对数组进行排序,并返回排序后的新数组 newArr
  • 时间复杂度: O(n+k)

    找出最大值和最小值的循环遍历了数组 nums 一次,时间复杂度为O(n) ,其中 n是数组 nums 的长度。
    统计元素出现次数的循环也遍历了数组 nums 一次,时间复杂度为O(n) 。
    根据计数数组重建排序后的数组的循环遍历了计数数组 arr 一次,时间复杂度为O(k) ,其中k是计数数组的长度(k=max - min +1)。
    总的时间复杂度为O(n+k)。

/*** @param {number[]} nums* @return {number[]}*/
var sortArray = function (nums) {// 找最大最小值let max = 0;let min = 0;for (let i = 0; i < nums.length; i++) {max = max > nums[i] ? max : nums[i];min = min < nums[i] ? min : nums[i];}const newArr = [];// 初始化数组长度为参数长度const arr = new Array(max - min + 1).fill(0);// 统计每一个值出现的次数for (let i = 0; i < nums.length; i++) {let arrIndex = nums[i] - min;if (arr[arrIndex] !== undefined) {arr[arrIndex] += 1;} else {arr[arrIndex] = 1;}}// 把有值的数据放到新数组里for (let i = 0; i < arr.length; i++) {const list = new Array(arr[i]).fill(min + i);newArr.push(...list);}return newArr;
};

相关文章:

leetcode 912. 排序数组

912. 排序数组 912. 排序数组 题目 给你一个整数数组 nums&#xff0c;请你将该数组升序排列。 你必须在 不使用任何内置函数 的情况下解决问题&#xff0c;时间复杂度为 O(nlog(n))&#xff0c;并且空间复杂度尽可能小。 示例 1&#xff1a; 输入&#xff1a;nums [5,2,3,1…...

【芯片设计】NPU芯片前端设计工程师面试记录·20250227

应聘公司 某NPU/CPU方向芯片设计公司。 小声吐槽两句,前面我问了hr需不需要带简历,hr不用公司给打好了,然后我就没带空手去的。结果hr小姐姐去开会了,手机静音( Ĭ ^ Ĭ )面试官、我、另外的hr小姐姐都联系不上,结果就变成了两个面试官和我一共三个人在会议室里一人拿出…...

BUU40 [CSCCTF 2019 Qual]FlaskLight1【SSTI】

模板&#xff1a; {{.__class__.__base__.__subclasses__()[80].__init__.__globals__[__builtins__].eval("__import__(os).popen(type flag.txt).read()")}} 是个空字符串&#xff0c;.__class__代表这个空字符串的类是什么&#xff08;这里是单引号双引号都行&a…...

WiFi IEEE 802.11协议精读:IEEE 802.11-2007,6,MAC service definition MAC服务定义

继续精读IEEE 802.11-2007 6&#xff0c;MAC service definition MAC服务定义 6.1 MAC服务概述 6.1.1 数据服务 此服务为对等逻辑链路控制&#xff08;LLC&#xff09;实体提供交换MAC服务数据单元&#xff08;MSDU&#xff09;的能力。为支持此服务&#xff0c;本地媒体访…...

2025学年安徽省职业院校技能大赛 “信息安全管理与评估”赛项 比赛样题任务书

2024-2025 学年广东省职业院校技能大赛 “信息安全管理与评估”赛项 技能测试试卷&#xff08;五&#xff09; 第一部分&#xff1a;网络平台搭建与设备安全防护任务书第二部分&#xff1a;网络安全事件响应、数字取证调查、应用程序安全任务书任务1 &#xff1a;内存取证&…...

VAE变分自编码器的初步理解

VAE的结构和原理 VAE由两部分组成&#xff1a; 编码器&#xff08;Encoder&#xff09;&#xff1a; 编码器负责将输入数据&#xff08;例如图像&#xff09;压缩成一个潜在空间&#xff08;latent space&#xff09;的表示。这个潜在空间不是一个固定的值&#xff0c;而是一个…...

2025 最新版鸿蒙 HarmonyOS 开发工具安装使用指南

为保证 DevEco Studio 正常运行&#xff0c;建议电脑配置满足如下要求&#xff1a; Windows 系统 操作系统&#xff1a;Windows10 64 位、Windows11 64 位内存&#xff1a;16GB 及以上硬盘&#xff1a;100GB 及以上分辨率&#xff1a;1280*800 像素及以上 macOS 系统 操作系统…...

Rider 安装包 绿色版 Win/Mac/Linux 适合.NET和游戏开发者使用 2025全栈开发终极指南:从零配置到企业级实战

下载链接&#xff1a; https://pan.baidu.com/s/1cfkJf6Zgxc1XfYrVpwtHkA?pwd1234 导语&#xff1a;JetBrains Rider以跨平台支持率100%、深度.NET集成和智能代码分析能力&#xff0c;成为2025年全栈开发者的首选工具。本文涵盖环境配置、核心功能、框架集成、性能调优、团队…...

Python常见面试题的详解24

1. 如何对关键词触发模块进行测试 要点 功能测试&#xff1a;验证正常关键词触发、边界情况及大小写敏感性&#xff0c;确保模块按预期响应不同输入。 性能测试&#xff1a;关注响应时间和并发处理能力&#xff0c;保证模块在不同负载下的性能表现。 兼容性测试&#xff1a;测…...

手机打电话时如何识别对方按下的DTMF按键的字符-安卓AI电话机器人

手机打电话时如何识别对方按下的DTMF按键的字符 --安卓AI电话机器人 一、前言 前面的篇章中&#xff0c;使用蓝牙电话拦截手机通话的声音&#xff0c;并对数据加工&#xff0c;这个功能出来也有一段时间了。前段时间有试用的用户咨询说&#xff1a;有没有办法在手机上&#xff…...

RabbitMQ操作实战

1.RabbitMQ安装 RabbitMQ Windows 安装、配置、使用 - 小白教程-腾讯云开发者社区-腾讯云下载erlang&#xff1a;http://www.erlang.org/downloads/https://cloud.tencent.com/developer/article/2192340 Windows 10安装RabbitMQ及延时消息插件rabbitmq_delayed_message_exch…...

IDEA 2024.1 最新永久可用(亲测有效)

今年idea发布了2024.1版本&#xff0c;这个版本带来了一系列令人兴奋的新功能和改进。最引人注目的是集成了更先进的 AI 助手&#xff0c;它现在能够提供更复杂的代码辅助功能&#xff0c;如代码自动补全、智能代码审查等&#xff0c;极大地提升了开发效率。此外&#xff0c;用…...

【R包】pathlinkR转录组数据分析和可视化利器

介绍 通常情况下&#xff0c;基因表达研究如微阵列和RNA-Seq会产生数百到数千个差异表达基因&#xff08;deg&#xff09;。理解如此庞大的数据集的生物学意义变得非常困难&#xff0c;尤其是在分析多个条件和比较的情况下。该软件包利用途径富集和蛋白-蛋白相互作用网络&…...

RPA 与 AI 结合:开启智能自动化新时代

RPA 与 AI 结合&#xff1a;开启智能自动化新时代 在当今数字化快速发展的时代&#xff0c;企业面临着海量的数据处理和复杂的业务流程&#xff0c;如何提高效率、降低成本、优化业务流程成为了企业关注的焦点。而 RPA&#xff08;Robotic Process Automation&#xff0c;机器…...

[免费]Springboot+Vue在线文档管理系统【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的SpringbootVue在线文档管理系统&#xff0c;分享下哈。 项目视频演示 【免费】SpringBootVue在线文档管理系统 Java毕业设计_哔哩哔哩_bilibili 项目介绍 随着科学技术的飞速发展&#xff0c;社会的方方面…...

内容选题与商业布局

内容选题与商业布局 提示词 1&#xff1a;人群链&#xff08;User Chain&#xff09;提示词 2&#xff1a;需求链&#xff08;Demand Chain&#xff09;提示词 3&#xff1a;环境 需求 优势 三要素提示词 4&#xff1a;垂直于“人性”而非只“赛道”提示词 5&#xff1a;基于…...

文字描边实现内黄外绿效果

网页使用 <!DOCTYPE html> <html> <head> <style> .text-effect {color: #ffd700; /* 黄色文字 */-webkit-text-stroke: 2px #008000; /* 绿色描边&#xff08;兼容Webkit内核&#xff09; */text-stroke: 2px #008000; /* 标准语法 *…...

网络协议 HTTP、HTTPS、HTTP/1.1、HTTP/2 对比分析

1. 基本定义 HTTP&#xff08;HyperText Transfer Protocol&#xff09; 应用层协议&#xff0c;用于客户端与服务器之间的数据传输&#xff08;默认端口 80&#xff09;。 HTTP/1.0&#xff1a;早期版本&#xff0c;每个请求需单独建立 TCP 连接&#xff0c;效率低。HTTP/1.1&…...

千峰React:Hooks(上)

什么是Hooks ref引用值 普通变量的改变一般是不好触发函数组件的渲染的&#xff0c;如果想让一般的数据也可以得到状态的保存&#xff0c;可以使用ref import { useState ,useRef} from reactfunction App() {const [count, setCount] useState(0)let num useRef(0)const h…...

salesforce 为什么无法关闭task,显示:insufficient access rights on object id

在 Salesforce 中&#xff0c;如果你在尝试关闭任务&#xff08;Task&#xff09;时遇到 “Insufficient access rights on object id” 错误&#xff0c;通常是由于以下几种可能的权限问题导致的&#xff1a; 1. 任务的所有权问题 Salesforce 中的任务&#xff08;Task&…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

快速排序算法改进:随机快排-荷兰国旗划分详解

随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...

TJCTF 2025

还以为是天津的。这个比较容易&#xff0c;虽然绕了点弯&#xff0c;可还是把CP AK了&#xff0c;不过我会的别人也会&#xff0c;还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...