网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索

 
 
 
日一二三四五六
       
       
       
       
       
       

签到排名:今日本吧第个签到,

本吧因你更精彩,明天继续来努力!

本吧签到人数:0

一键签到
成为超级会员,使用一键签到
一键签到
本月漏签0次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行补签。
连续签到:天  累计签到:天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
11月06日漏签0天
c++吧 关注:640,958贴子:2,116,394
  • 看贴

  • 图片

  • 吧主推荐

  • 游戏

  • 18回复贴,共1页
<<返回c++吧
>0< 加载中...

怎么判断一个数列的排列是否正确,有多少错了?

  • 只看楼主
  • 收藏

  • 回复
  • NinsunClosear
  • <
    11
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
例如,数列:1,2,5,3,4,我们可以很清楚的看到5的位置错了
再比如,2,1,3,4,5,我们也可以很清楚的知道到,1,2的顺序反了
但是,我们怎么判断有多少个数的位置错了?
第一个数列,5的顺序错了,应该是错1个
但第二个数列,1,2的顺序反了,但是也应该算1个位置错了吧……但是要说错了2个也无可厚非……
所以,有没有什么标准的判断依据,判断一个数列里面顺序错误的数有几个呢?
更具体一点,我想判断一个数列里面位置错误的数的数量,怎么写算法呢……


  • NinsunClosear
  • <
    11
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
而以上的例子只是5个数字,有一个错误的情况,那么扩展到N个数字,不知道有多少顺序错误的情况下,有什么好的算法来计算顺序错误的数字的个数呢……


2025-11-06 18:54:37
广告
不感兴趣
开通SVIP免广告
  • NinsunClosear
  • <
    11
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
只需要考虑等差数列,差值为1的情况……


  • 恋魂熴憮
  • |
    7
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
写一个排序算法,排多少次就是多少个数错了,
另外认为12534是3个数错了,而不是1个


  • invisible蜻蜓
  • <
    11
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
2317456哪几个的位置错了


  • nadesico19
  • +
    13
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
第一感觉可以用Levenshtein Distance处理,将排好序的数列和原数列求距离,再统计出其中删除与插入的数量。删除与插入的数量必定一致,用总的距离减去这个数量即可。
举例来说:
[2,3,1,4,5]的距离是2,其中包含一次对1的删除和插入,因此结果为1。
[5,4,3,2,1]的距离是4,按照一般算法会对5、4、2、1进行了重置,因此结果就为4。
未实测。。。


  • 顾影怜谁
  • ==
    10
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
第二个太笼统了吧,有多少排错没有标准啊
这种基本有序的就是把无序的挑出来,然后再插入排序就好了


  • 蹲厕唱唱歌
  • &
    9
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
if 前面>后面
static sum++


登录百度账号

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频!
  • 贴吧页面意见反馈
  • 违规贴吧举报反馈通道
  • 贴吧违规信息处理公示
  • 18回复贴,共1页
<<返回c++吧
分享到:
©2025 Baidu贴吧协议|隐私政策|吧主制度|意见反馈|网络谣言警示