当前位置: 首页 > 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&…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验

Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

redis和redission的区别

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