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

把数组里面数值排成最小的数

 问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。例如输入数组{12,  567},则输出这两个能排成的最小数字12567。请给出解决问题的算法,并证明该算法。

      思路:先将整数数组转为字符串数组,然后字符串数组进行排序,最后依次输出字符串数组即可。这里注意的是字符串的比较函数需要重新定义,不是比较a和b,而是比较ab与 ba。如果ab < ba,则a < b;如果ab > ba,则a > b;如果ab = ba,则a = b。比较函数的定义是本解决方案的关键。

      证明:为什么这样排个序就可以了呢?简单证明一下。根据算法,如果a < b,那么a排在b前面,否则b排在a前面。可利用反证法,假设排成的最小数字为xxxxxx,并且至少存在一对字符串满足这个关系:a > b,但是在组成的数字中a排在b前面。根据a和b出现的位置,分三种情况考虑:

      (1)xxxxab,用ba代替ab可以得到xxxxba,这个数字是小于xxxxab,与假设矛盾。因此排成的最小数字中,不存在上述假设的关系。

      (2)abxxxx,用ba代替ab可以得到baxxxx,这个数字是小于abxxxx,与假设矛盾。因此排成的最小数字中,不存在上述假设的关系。

      (3)axxxxb,这一步证明麻烦了一点。可以将中间部分看成一个整体ayb,则有ay < ya,yb < by成立。将ay和by表示成10进制数字形式,则有下述关系式,这里a,y,b的位数分别为n,m,k。

        关系1: ay < ya => a * 10^m + y < y * 10^n + a => a * 10^m - a < y * 10^n - y => a( 10^m - 1)/( 10^n - 1) < y

        关系2: yb < by => y * 10^k + b < b * 10^m + y => y * 10^k - y < b * 10^m - b => y < b( 10^m -1)/( 10^k -1) 

        关系3: a( 10^m - 1)/( 10^n - 1) < y < b( 10^m -1)/( 10^k -1)  => a/( 10^n - 1)< b/( 10^k -1) => a*10^k - a < b * 10^n - b =>a*10^k + b < b * 10^n + a => a < b

       这与假设a > b矛盾。因此排成的最小数字中,不存在上述假设的关系。

       综上所述,得出假设不成立,从而得出结论:对于排成的最小数字,不存在满足下述关系的一对字符串:a > b,但是在组成的数字中a出现在b的前面。从而得出算法是正确的。

      参考代码:

//重新定义比较函数对象
struct compare
{bool operator() (const string &src1, const string &src2){string s1 = src1 + src2;string s2 = src2 + src1;return s1 < s2;   //升序排列,如果改为s1 > s2则为逆序排列}
};
//函数功能 : 把数组排成最小的数
//函数参数 : pArray为数组,num为数组元素个数  
//返回值 :   无
void ComArrayMin(int *pArray, int num)
{int i;string *pStrArray = new string[num];for(i = 0; i < num; i++) //将数字转换为字符串{	stringstream stream;stream<<pArray[i];stream>>pStrArray[i];}sort(pStrArray, pStrArray + num, compare()); //字符串数组排序for(i = 0; i < num; i++) //打印字符串数组cout<<pStrArray[i];cout<<endl;delete [] pStrArray;
}

相关文章:

把数组里面数值排成最小的数

问题描述&#xff1a;输入一个正整数数组&#xff0c;将它们连接起来排成一个数&#xff0c;输出能排出的所有数字中最小的一个。例如输入数组{12, 567}&#xff0c;则输出这两个能排成的最小数字12567。请给出解决问题的算法&#xff0c;并证明该算法。 思路&#xff1a;先将…...

云his系统源码 SaaS应用 基于Angular+Nginx+Java+Spring开发

云his系统源码 SaaS应用 功能易扩 统一对外接口管理 一、系统概述&#xff1a; 本套云HIS系统采用主流成熟技术开发&#xff0c;软件结构简洁、代码规范易阅读&#xff0c;SaaS应用&#xff0c;全浏览器访问前后端分离&#xff0c;多服务协同&#xff0c;服务可拆分&#xff…...

小红书场景营销怎么做?场景营销主要模式有哪些

小红书作为新兴媒体领域的佼佼者&#xff0c;凭借着生动&#xff0c;直观&#xff0c;代入感等元素的分享推荐收揽了巨额的流量。但是&#xff0c;随着时代的脚步逐渐加快&#xff0c;发展和变革随之涌来&#xff0c;传统的营销已经无法满足。所以场景营销就出现了。今天就来和…...

c++基础——数组

数组数组是存放相同类型对象的容器&#xff0c;数组中存放的对象没有名字&#xff0c;而是要通过其所在的位置访问。数组的大小是固定的&#xff0c;不能随意改变数组的长度。定义数组数组的声明形如 a[b]&#xff0c;其中&#xff0c;a 是数组的名字&#xff0c;b 是数组中元素…...

odoo15 登录界面的标题自定义

odoo15 登录界面的标题自定义 原代码中查询:<title>Odoo<title> <html> <head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>Odoo</title><link rel="shortcut icon…...

【内网服务通过跳板机和公网通信】花生壳内网穿透+Nginx内网转发+mqtt服务搭建

问题&#xff1a;服务不能暴露公网 客户的主机不能连外网&#xff0c;服务MQTT服务部署在内网。记做&#xff1a;p1 (computer 1)堡垒机&#xff08;跳板机&#xff09;可以连外网&#xff0c;内网IP 和 MQTT服务在同一个网段。记做&#xff1a;p2 (computer 2)对他人而言&…...

【多线程常见面试题】

谈谈 volatile关键字的用法? volatile能够保证内存可见性,强制从主内存中读取数据,此时如果有其他线程修改被volatile修饰的变量,可以第一时间读取到最新的值 Java多线程是如何实现数据共享的? JVM把内存分成了这几个区域: 方法区,堆区,栈区,程序计数器&#xff1b; 其中堆区…...

深度剖析指针(下)——“C”

各位CSDN的uu们你们好呀&#xff0c;今天小雅兰的内容还是我们的指针呀&#xff0c;上两篇博客我们基本上已经把知识点过了一遍&#xff0c;这篇博客就让小雅兰来带大家看一些和指针有关的题目吧&#xff0c;现在&#xff0c;就让我们进入指针的世界吧 复习&#xff1a; 数组和…...

爬虫与反爬虫技术简介

互联网的大数据时代的来临&#xff0c;网络爬虫也成了互联网中一个重要行业&#xff0c;它是一种自动获取网页数据信息的爬虫程序&#xff0c;是网站搜索引擎的重要组成部分。通过爬虫&#xff0c;可以获取自己想要的相关数据信息&#xff0c;让爬虫协助自己的工作&#xff0c;…...

Pag的2D渲染执行流程

Pag的渲染 背景 根据Pag文章里面说的&#xff0c;Pag之前长时间使用的Skia库作为底层渲染引擎。但由于Skia库体积过大&#xff0c;为了保证通用型&#xff08;比如兼容CPU渲染&#xff09;做了很多额外的事情。所以Pag的工程师们自己实现了一套2D图形框架替换掉Skia&#xff…...

k8s 概念说明,k8s面试题

什么是Kubernetes&#xff1f; Kubernetes是一种开源容器编排系统&#xff0c;可自动化应用程序的部署、扩展和管理。 Kubernetes 中的 Master 组件有哪些&#xff1f; Kubernetes 中的 Master 组件包括 API Server、etcd、Scheduler 和 Controller Manager。 Kubernetes 中的…...

Docker--(四)--搭建私有仓库(registry、harbor)

私有仓库----registry官方提供registry仓库管理&#xff08;推送、删除、下载&#xff09;私有仓库----harbor私有镜像仓库1.私有仓库----registry官方提供 Docker hub官方已提供容器镜像registry,用于搭建私有仓库 1.1 镜像拉取、运行、查看信息、测试 (一) 拉取镜像 # dock…...

Invalid <url-pattern> [sso.action] in filter mapping

Tomcat 8.5.86版本启动web项目报错Caused by: java.lang.IllegalArgumentException: Invalid <url-pattern> [sso.action] in filter mapping 查看项目的web.xml文件相关片段 <filter-mapping><filter-name>SSOFilter</filter-name><url-pattern&g…...

【11】linux命令每日分享——useradd添加用户

大家好&#xff0c;这里是sdust-vrlab&#xff0c;Linux是一种免费使用和自由传播的类UNIX操作系统&#xff0c;Linux的基本思想有两点&#xff1a;一切都是文件&#xff1b;每个文件都有确定的用途&#xff1b;linux涉及到IT行业的方方面面&#xff0c;在我们日常的学习中&…...

Newman+Jenkins实现接口自动化测试

一、是什么Newman Newman就是纽曼手机这个经典牌子&#xff0c;哈哈&#xff0c;开玩笑啦。。。别当真&#xff0c;简单地说Newman就是命令行版的Postman&#xff0c;查看官网地址。 Newman可以使用Postman导出的collection文件直接在命令行运行&#xff0c;把Postman界面化运…...

MySQL:事务+@Transactional注解

事务 本章从了解为什么需要事务到讲述事务的四大特性和概念&#xff0c;最后讲述MySQL中的事务使用语法以及一些需要注意的性质。 再额外讲述一点Springboot中Transactional注解的使用。 1.为什么需要事务&#xff1f; 我们以用户转账为例&#xff0c;假设用户A和用户B的银行账…...

数字IC手撕代码--低功耗设计 Clock Gating

背景介绍芯片功耗组成中&#xff0c;有高达 40%甚至更多是由时钟树消耗掉的。这个结果的原因也很直观&#xff0c;因 为这些时钟树在系统中具有最高的切换频率&#xff0c;而且有很多时钟 buffer&#xff0c;而且为了最小化时钟 延时&#xff0c;它们通常具有很高的驱动强度。 …...

易基因|m6A RNA甲基化研究的数据挖掘思路:干货系列

大家好&#xff0c;这里是专注表观组学十余年&#xff0c;领跑多组学科研服务的易基因。关于m6A甲基化研究思路&#xff08;1&#xff09;整体把握m6A甲基化图谱特征&#xff1a;m6A peak数量变化、m6A修饰基因数量变化、单个基因m6A peak数量分析、m6A peak在基因元件上的分布…...

【微信小程序】-- 页面配置(十八)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &…...

玩好 StarRocks,大厂 offer 接不完!|字节跳动、小红书、京东物流、唯品会、腾讯音乐要的就是你!

求职黄金季即将到来&#xff0c;你准备好迎接你的 dream offer 了吗&#xff1f;StarRocks 自创立以来&#xff0c;一直主张为用户创造极速统一的数据分析新范式&#xff0c;让数据驱动创新&#xff0c;而优秀的大数据人才对推动创新有着至关重要的作用。因此&#xff0c;我们推…...

Argo CD 集成 Helmfile 插件:实现 GitOps 下复杂应用声明式部署

1. 项目概述与核心价值如果你正在使用 Argo CD 管理 Kubernetes 集群&#xff0c;并且你的应用清单是由 Helmfile 来编排的&#xff0c;那么travisghansen/argo-cd-helmfile这个项目很可能就是你一直在寻找的“粘合剂”。简单来说&#xff0c;它是一个专门为 Argo CD 设计的 He…...

日志收集与分析平台搭建:ELK Stack实战入门

为什么测试工程师需要ELK在软件测试的日常工作中&#xff0c;日志是我们最熟悉也最依赖的“侦探工具”。无论是定位功能缺陷、分析性能瓶颈&#xff0c;还是复现偶发性Bug&#xff0c;测试人员都离不开日志。然而&#xff0c;随着微服务架构、容器化部署和分布式系统的普及&…...

60 秒应急窗口下 AI 钓鱼攻击防御体系构建与工程实践

摘要 2026 年网络钓鱼攻击呈现秒级入侵、全域渗透、AI 驱动的显著特征&#xff0c;钓鱼邮件抵达至用户输入敏感信息的中位时间仅 60 秒&#xff0c;勒索软件攻击频率约每 2 秒一起&#xff0c;AI 自动化鱼叉式钓鱼点击率高达 54%&#xff0c;传统防御机制已无法适配当前威胁节奏…...

当三维基因组“打结”:从罕见病到癌症,那些被折叠改变的生命密码

当三维基因组“打结”&#xff1a;从罕见病到癌症&#xff0c;那些被折叠改变的生命密码 想象一下&#xff0c;如果把人类基因组比作一条长达两米的毛线&#xff0c;它需要被精巧地折叠进直径仅几微米的细胞核中。这种看似不可能的折叠并非随机——它遵循着严格的拓扑规则&…...

告别疲劳计算烦恼:用nCode DesignLife搞定汽车悬架非线性载荷分析(附信号处理技巧)

告别疲劳计算烦恼&#xff1a;用nCode DesignLife搞定汽车悬架非线性载荷分析&#xff08;附信号处理技巧&#xff09; 悬架系统作为汽车底盘的核心部件&#xff0c;其疲劳寿命直接关系到整车可靠性与安全性。但在实际工程分析中&#xff0c;工程师们常常被一个棘手问题困扰&am…...

【JSON-RPC远程过程调用组件库】测试报告

RPC 框架测试报告一、项目背景 本项目是一个基于 C 实现的轻量级 RPC&#xff08;远程过程调用&#xff09;框架&#xff0c;旨在解决分布式系统中服务间通信的复杂性。框架提供三大核心能力&#xff1a;基础 RPC 远程调用&#xff08;同步/异步/回调三种模式&#xff09;、基于…...

从Kaggle竞赛到实战:基于XGBoost的Otto多分类产品识别系统构建

1. 从Kaggle竞赛到真实业务场景的跨越 第一次接触Otto数据集是在2015年的Kaggle竞赛上&#xff0c;当时只觉得这是个典型的多分类问题。直到去年为某跨境电商平台搭建商品自动分类系统时&#xff0c;我才真正理解这个案例的实战价值——90%的参赛者只关注模型精度&#xff0c;而…...

AI工具搭建自动化视频生成Quick Sync

# Quick Sync&#xff1a;AI驱动的自动化视频生成技术实战解析 前阵子团队接了个批量短视频生成的项目&#xff0c;要在短时间内产出数百条产品演示视频。一开始想着一个个用Premiere剪&#xff0c;但算算时间&#xff0c;光是渲染就够呛。后来试用了几种自动化方案&#xff0c…...

CANN/asc-devkit FreeAllEvent API文档

FreeAllEvent 【免费下载链接】asc-devkit 本项目是CANN 推出的昇腾AI处理器专用的算子程序开发语言&#xff0c;原生支持C和C标准规范&#xff0c;主要由类库和语言扩展层构成&#xff0c;提供多层级API&#xff0c;满足多维场景算子开发诉求。 项目地址: https://gitcode.c…...

MySQL 基础:SELECT、WHERE、JOIN 的第一次使用

不用怕数据库&#xff0c;跟着这三个单词&#xff0c;你就能查到你想要的一切。欢迎来到 《大一突围》 专栏。很多大一同学第一次接触 MySQL&#xff0c;看到“数据库”三个字就觉得很难。其实&#xff0c;你日常生活中每天都在“查数据”——查成绩、翻通讯录、筛选淘宝商品……...