(排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】

news/2024/4/15 14:56:39

❓ 剑指 Offer 45. 把数组排成最小的数

难度:中等

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: “102”

示例 2:

输入: [3,30,34,5,9]
输出: “3033459”

提示:

  • 0 < nums.length <= 100

说明:

  • 输出结果可能非常大,所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0

💡思路:

可以看成是一个排序问题,在比较两个字符串 s1s2 的大小时,应该比较的是 s1+s2s2+s1 的大小:

  • 如果 s1+s2 < s2+s1,那么应该把 s1 排在前面,否则应该把 s2 排在前面。

总体流程:

  1. 初始化: 字符串列表 strs ,保存各数字的字符串格式;
  2. 列表排序: 应用以上 “排序判断规则” ,对 strs 执行排序;
  3. 返回结果: 拼接 strs 中的所有字符串,并返回。

法一:快速排序

需修改快速排序函数中的排序判断规则。字符串大小(字典序)对比的实现方法:

  • C++ 中可直接用 < , >
  • Java 中使用函数 A.compareTo(B)

法二:内置函数

  • C++ 定义为 (string& x, string& y){ return x + y < y + x; } ;
  • Java 定义为 (x, y) -> (x + y).compareTo(y + x);

🍁代码:(C++、Java)

法一:快速排序
C++

class Solution {
private:void quickSort(vector<string>& strs, int l, int r){if(l >= r) return;int i = l + 1, j = r;while(i <= j){//从前往后找第一个比str[l] 大的字符串while(i <= j && strs[i] + strs[l] <= strs[l] + strs[i])i++;//从后往前找第一个比str[l] 小的字符串while(i <= j && strs[j] + strs[l] >= strs[l] + strs[j])j--;//交换if(i < j)swap(strs[i++], strs[j--]);}swap(strs[l], strs[j]);quickSort(strs, l, j - 1);quickSort(strs, j + 1, r);}
public:string minNumber(vector<int>& nums) {// 1. 初始化vector<string> strs;for(int i = 0; i < nums.size(); i++){strs.push_back(to_string(nums[i]));}// 2. 排序quickSort(strs, 0, strs.size() - 1);// 3. 返回结果string ans;for(string s : strs){ans.append(s);}return ans;}
};

Java

class Solution {private void quickSort(String[] strs, int l, int r){if(l >= r) return;int i = l + 1, j = r;String temp;while(i <= j){//从前往后找第一个比str[l] 大的字符串while(i <= j && (strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0)i++;//从后往前找第一个比str[l] 小的字符串while(i <= j && (strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0)j--;//交换if(i < j){temp = strs[i];strs[i++] = strs[j];strs[j--] = temp;}}//此时j + 1 = i,strs[i]左边的字符串一定比strs[l]小,strs[j]右边的字符串一定比strs[l]大temp = strs[l];strs[l] = strs[j];strs[j] = temp;quickSort(strs, l, j - 1);quickSort(strs, j + 1, r);}public String minNumber(int[] nums) {// 1. 初始化String[] strs = new String[nums.length];for(int i = 0; i < nums.length; i++){strs[i] = String.valueOf(nums[i]);}// 2. 排序quickSort(strs, 0, strs.length - 1);// 3. 返回结果StringBuilder ans = new StringBuilder();for(String s : strs){ans.append(s);}return ans.toString();}
}

法二:内置函数
C++

class Solution {
public:string minNumber(vector<int>& nums) {// 1. 初始化vector<string> strs;for(int i = 0; i < nums.size(); i++){strs.push_back(to_string(nums[i]));}// 2. 内置函数排序sort(strs.begin(), strs.end(), [](string& x, string& y){return x + y < y + x;});// 3. 返回结果string ans;for(string s : strs){ans.append(s);}return ans;}
};

Java

class Solution {public String minNumber(int[] nums) {// 1. 初始化String[] strs = new String[nums.length];for(int i = 0; i < nums.length; i++){strs[i] = String.valueOf(nums[i]);}// 2. 内置函数排序Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));// 3. 返回结果StringBuilder ans = new StringBuilder();for(String s : strs){ans.append(s);}return ans.toString();}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn),其中 n 为数组的长度,使用快排或内置函数的平均时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) ,最差为 O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度 O ( n ) O(n) O(n),字符串列表 strs 占用线性大小的额外空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/1052179.html

相关文章

方案:AI边缘计算智慧工地解决方案

一、方案背景 在工程项目管理中&#xff0c;工程施工现场涉及面广&#xff0c;多种元素交叉&#xff0c;状况较为复杂&#xff0c;如人员出入、机械运行、物料运输等。特别是传统的现场管理模式依赖于管理人员的现场巡查。当发现安全风险时&#xff0c;需要提前报告&#xff0…

服务器在使用过程中如何保护数据

在租用服务器搭建网站运营的时候&#xff0c;除了保证网站的正常运营之外&#xff0c;对于网站数据安全的保护也不容忽视&#xff0c;那么租用服务器的 时候如何做好防御呢&#xff0c;租用服务器建站的时候如何做好数据库的安全工作呢&#xff1f; 数据库的备份工作 对于数据库…

MyBatis plus 多数据源实现

1. 项目背景 最近写文章发布到【笑小枫】小程序和我的个人网站上&#xff0c;因为个人网站用的是halo框架搭建&#xff0c;两边数据结构不一致&#xff0c;导致我每次维护文章都需要两边维护&#xff0c;这就很烦~ 于是&#xff0c;本文就诞生了。通过项目连接这两个数据库&a…

二、1.保护模式

访问外部硬件有两个方式&#xff1a; 将某个外设的内存映射到一定范围的地址空间中&#xff0c; CPU 通过地址总线访问该内存区域时会落到外设 的内存中&#xff0c;这种映射让 CPU 访问外设的内存就如同访问主板上的物理内存一样外设是通过 IO 接口与 CPU 通信的&#xff0c;…

在Hive/Spark上执行TPC-DS基准测试 (PARQUET格式)

在上一篇文章:《在Hive/Spark上运行执行TPC-DS基准测试 (ORC和TEXT格式)》中,我们介绍了如何使用 hive-testbench 在Hive/Spark上执行TPC-DS基准测试,同时也指出了该项目不支持parquet格式。 如果我们想要生成parquet格式的测试数据,就需要使用其他工具了。本文选择使用另…

linux定时备份MySQL数据库循环删除前30天的备份文件

linux定时备份MySQL数据库循环删除前30天的备份文件 一、 检查有没安装crond,如果没有&#xff0c;先安装 1、先检查一下有没有cron rpm -qa|grep cron如果输入上面命令有如下显示&#xff0c;则不需要安装 2、没有安装的话&#xff0c;就使用一下命令安装 yum -y install …

【Go 基础篇】Go语言获取用户终端输入:实现交互式程序的关键一步

介绍 在许多编程场景中&#xff0c;我们需要编写交互式程序&#xff0c;以便用户可以在终端中输入数据并与程序进行交互。Go语言提供了丰富的方式来获取用户终端输入&#xff0c;使得编写交互式程序变得简单而有趣。本篇博客将深入探讨Go语言中获取用户终端输入的各种方法&…

“深入探索JVM:Java虚拟机背后的奥秘“

标题&#xff1a;深入探索JVM&#xff1a;Java虚拟机背后的奥秘 摘要&#xff1a;本文将深入探索Java虚拟机&#xff08;JVM&#xff09;的内部工作原理和关键组成部分&#xff0c;揭示JVM背后的奥秘。通过对类加载机制、内存管理、垃圾回收、即时编译等方面的详细介绍&#x…

2023国赛数学建模思路 - 案例:异常检测

文章目录 赛题思路一、简介 -- 关于异常检测异常检测监督学习 二、异常检测算法2. 箱线图分析3. 基于距离/密度4. 基于划分思想 建模资料 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 一、简介 – 关于异常…

PHP 房产网站系统Dreamweaver开发mysql数据库web结构php编程计算机网页项目

一、源码特点 PHP 房产网站系统是一套完善的WEB设计系统&#xff0c;对理解php编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 源码 https://download.csdn.net/download/qq_41221322/88233553 论文 https://download…

CSS中的display属性有哪些值?它们的作用?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ CSS display 属性的不同取值和作用1. block2. inline3. inline-block4. none5. flex6. grid7. table、table-row、table-cell8. list-item9. inline-table、table-caption、table-column 等 ⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#x…

常见的Redux问题

在React中使用Redux的面试题目通常涵盖了Redux的基本概念、工作原理、如何在React应用中集成Redux等方面。以下是一些常见的Redux问题&#xff1a; Redux的核心概念&#xff1a; 1、什么是Redux&#xff1f;它解决了什么问题&#xff1f; 它是一个状态管理库&#xff0c;解决…

圆的反演 hdu 6097

欢迎关注更多精彩 关注我&#xff0c;学习常用算法与数据结构&#xff0c;一题多解&#xff0c;降维打击。 题目大意 http://acm.hdu.edu.cn/showproblem.php?pid6097 有一个圆C&#xff0c;它的圆心是O(0,0), 半径是r。 在C内部或边界上有两点P和Q&#xff0c;OPOQ。 求解…

三维模型OSGB格式轻量化的纹理压缩和质量保持分析

三维模型OSGB格式轻量化的纹理压缩和质量保持分析 在三维模型应用中&#xff0c;纹理数据是一个重要的部分&#xff0c;可以为模型增加更多的真实感和细节。但是&#xff0c;由于纹理数据通常会占用大量的存储空间和传输带宽&#xff0c;因此&#xff0c;在OSGB格式轻量化处理中…

4.物联网LWIP之C/S编程,实现服务器大小写转换

LWIP配置 服务器端实现 客户端实现 错误分析 一。LWIP配置&#xff08;FREERTOS配置&#xff0c;ETH配置&#xff0c;LWIP配置&#xff09; 1.FREERTOS配置 为什么要修改定时源为Tim1&#xff1f;不用systick&#xff1f; 原因&#xff1a;HAL库与FREERTOS都需要使用systi…

Modbus_TCP协议如何使用?

1 驱动简介 网关支持标准的Modbus-TCP协议&#xff0c;支持Modbus-TCP协议的设备&#xff08;例如智能仪表、电表等&#xff09;&#xff0c;都可以通过此协议直接通讯&#xff0c;实现远程采集、监控、控制设备的功能。 从站号&#xff1a;默认为1&#xff0c;需要查看设备说…

【C++】STL——set的介绍和使用、set的构造函数、set的迭代器、set的容量和增删查改函数

文章目录 1.set的介绍2.set的使用2.1set的构造函数2.2set的迭代器2.3set的容量函数2.4set的增删查改函数 1.set的介绍 set的介绍 &#xff08;1&#xff09;set是按照一定次序存储元素的容器。 &#xff08;2&#xff09;在set中&#xff0c;元素的value也标识它(value就是key…

JUC--阻塞队列

目录 问题引出 一.单端阻塞队列&#xff08;BlockingQueue&#xff09; 二.双端阻塞队列&#xff08;BlockingDeque&#xff09; 三.延迟队列&#xff08;DelayQueue&#xff09; 问题引出 由于实现消费者-生产者模型&#xff0c;每一次实现都比较麻烦&#xff0c;比如sych…

ios 声网agora 音视频直播场景下的集成总结

文章目录 一、前言二、视频会议场景2.1 场景描述2.2 功能列表三、电商直播场景3.1 场景描述3.2 功能列表3.3 技术方案四、声网iOS SDK集成4.1 集成4.2 示例demo4.3 核心代码4.3.1 初始化4.3.2 加入频道4.3.3 切换身份4.4.4 连麦4.4 相关问题4.4.1 监听观众角色用户事件五、相关…

MySQL 中常用函数详解

MySQL 提供了一系列丰富的函数&#xff0c;这些函数在数据处理中起着重要的作用。下面&#xff0c;我们将详细介绍一些最常用的 MySQL 函数&#xff0c;包括字符串函数、数学函数、日期和时间函数、聚合函数等。 1. 字符串函数 1.1 CONCAT() CONCAT() 函数用于连接两个或多个字…
最新文章