栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

蓝桥杯java-排序(填空题2020省赛)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

蓝桥杯java-排序(填空题2020省赛)

题目描述:
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

小蓝最近学习了一些排序算法,其中冒泡排序让他印象深刻。

在冒泡排序中,每次只能交换相邻的两个元素。

小蓝发现,如果对一个字符串中的字符排序,只允许交换相邻的两个字符, 则在所有可能的排序方案中,冒泡排序的总交换次数是最少的。

例如,对于字符串 lanlan 排序,只需要 11 次交换。对于字符串 qiaoqiao 排序,总共需要 44 次交换。

小蓝找到了很多字符串试图排序,他恰巧碰到一个字符串,需要 100100 次交 换,可是他忘了吧这个字符串记下来,现在找不到了。

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串,对 该串的字符排序,正好需要 100100 次交换。如果可能找到多个,请告诉小蓝最短的那个。如果最短的仍然有多个,请告诉小蓝字典序最小的那个。

分析:
假设完全逆序,设长度为n,采用冒泡排序则移动次数为 n*(n-1)/2
a移动n-1次,b移动n-2次…字典序倒数第二大的字母只移动1次,字典序最大的字母不用移动
根据等差数列求和1+2+…+(n-2)+(n-1) = (n-1)*(1+n-1)/2
当n=15,移动次数105,移动次数大于100,又要求字典序最小,则把第六个字符移动到第一个位置,前五个字符后移一位。即:jonmlkihgfedcba

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/358270.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号