题目

1——100000数列按一定顺序排列,有一个数字排错,如何纠错?写出最好方法.两个数字呢?

提问时间：2020-07-30

答案

我觉得这个可以用类似于2分法莱进行查找出出错的那个数字.我把出错分为2中：
1. 相邻交换(1,2,3,5,4,)： 这种出错其实可以看成是5错,也可以看成是4错
2. 不相邻插入(1,2,4,5,3)：这种出错只有3是错的
考虑到这个,我用1-9做例子： 1-9一共9个数字,则出错有3中情况：
1. 出错的数字仍然在同一边比如（1,3,2,4,5,6,7,8,9）
2. 出错的数字在另外一边（1,3,4,5,6,2,7,8,9）
3. 出错的数字在中间（1,3,4,5,2,6,7,8,9）
观察可得
1. 如果中间的数字没变,说明该错出现在同一边（如1）
2. 如果中间的数字比相邻左边的数字相差1（绝对值）,且比相邻右边数字相差1（绝对值）,说明该错非中间数字,继续递归左右两半,直到3或者4情况
3. 如果中间的数字比相邻左边的数字相差1（绝对值）,且比相邻右边数字相差不等于1（绝对值）,说明该错非中间数字,而是右边的数字,复原则结束
4. 如果中间的数字比相邻左边的数字相差不等于1（绝对值）,且比相邻右边数字相差等于1（绝对值）,说明该错非中间数字,而是左边的数字,复原则结束