算法-在数组中如何快速找出顺序不对的值

算法-在数组中如何快速找出顺序不对的值

甜柠檬 发布于 2017-06-29 字数 249 浏览 1306 回复 9

已知数组长度为100,且基本小到大排序,里面有仅有两个数字位置不对,但具体是那两个数字不知道,数字不重复,如何快速找出这两个值的位置。
例如:[199 201 204 205 。。288 900 389 390 491 592 693 。。。 798 600 1000 ]

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(9

归属感 2017-10-16 9 楼

要注意如果错的两个数相邻的话会产生更多的复杂情况,如
1 2 3 4 5 6 10 11 7 8 9
1 2 3 4 7 8 9 10 5 6 11

即使不相邻

1 2 3 4 7 8 9 10 5 11
这里错的是10还是5?仅仅和相邻元素比较是无法判断的。

因此仅仅比较相邻两个数是不够的

不难发现N个元素至少要全部遍历一遍才有可能找出答案,所以最佳的算法复杂度应该是o(N)
又注意到,如果存在a_k > a_m, k < m,则(a_k, a_m)中至少有一个是错误的(这样的对称为逆序对)。反过来,任意一个错误的元素,也至少存在一组(a_k, a_m)符合上述条件,且该数等于a_k或a_m。
那么思路就在于首先找出这样的逆序对。自然先从相邻元素入手:
(a_0, a_1), (a_1, a_2), ...
相邻元素两两比较
如果这样找出了两对逆序对,(a_k, a_k+1) (a_m, a_m+1), k<m那么:
1. 有公共元素,即a_k+1 = a_m
由于a_k > a_m > a_m+1, (a_k, a_m+1)也构成逆序对,因此三个数中有两个是错误的。
考虑两端的数a_k-1和a_m+2,正确的一个应该符合a_k-1 < a_n < a_m+2。逐个进行判断就可以区分出正确的一个;如果这三个数靠边(k = 0, 或者m = 99),一边的条件认为自动满足;如果有多个符合的,任意一个都可以认为是正确的,其他两个是错误的。注意到a_k > a_k+1 > a_k+2, 其实只需要进行a_k < a_k+3? a_k+2 > a_k-1?两次判断就足够了

没有公共元素
这种情况比较简单,每组中有一个错误的,一样是和前后元素a_k-1, a_k+2比较,找到符合顺序的一个

如果只出现了一对(a_k, a_k+1),这说明:1. 两个错误的元素相邻,为a_m和a_m+1 2. 错误元素满足a_m < a_m+1 3. a_k, a_k+1中,有且仅有一个是错误元素
这个不难证明,就不详细说了

因此只出现一对时有两种可能:a_k-1, a_k和 a_k+1, a_k+2
比较a_k-2 和 a_k+1,如果a_k-2 < a_k + 1,则可以认为a_k+1和a_k+2排序是正确的,错误元素为a_k-1和a_k;否则是a_k+1, a_k+2。如果k=0,那自然就是第二种了。

详细算法(这个算法并没有处理全部的异常情况,加注释的几行加进来也只是保证不会输出非法的结果):

int k = -1, m = -1;
int err1, err2; //Return Value
for(int i = 0; i < 99; i++)
{
if(a[i] > a[i+1])
{
if(k == -1)
k = i;
else
m = i;
}
}
//if(k == -1)
//throw new Exception("Error: not found");
if(m == -1)
{
if(k == 0 || a[k-2] > a[k+1])
{
//if(k == 98)
//throw new Exception("Error: find one only");
err1 = k + 1;
err2 = k + 2;
}
else
{
err1 = k - 1;
err2 = k;
}
}
else if(m == k + 1)
{
if(k + 3 >= 100 || a[k] < a[k+3])
{
err1 = k + 1;
err2 = k + 2;
}
else if(k == 0 || a[k-1] < a[k+2])
{
err1 = k;
err2 = k + 1;
}
else
{
err1 = k;
err2 = k + 2;
}
}
else
{
if(k == 0 || a[k-1] < a[k+1])
{
err1 = k;
}
else
{
err1 = k + 1;
}
if(a[m-1] < a[m+1])
{
err2 = m;
}
else
{
err2 = m + 1;
}
}

灵芸 2017-10-07 8 楼

第1个跟第2个比 如果第1个大 那么第1个顺序不对 排除第一个 否则不动
再用第2个跟第3个比 第2个比第3个大 排除第2个 否则不动
再用第3个跟第4个比 第3个比第4个大 排除第3个 否则不动
这样排除这些对于规模为100个的序列 大概需要比较99次

晚风撩人 2017-09-26 7 楼

1 2 3 4 5 6 10 11 7 8 9其实并没有歧义
因为10 11 7 8 9 都是顺序不同的数
假设数列时有小到大排列,如果出现顺序不同的数则必然出现两个集合
分歧的数的集合,受影响的数的集合
例如:
假设从1遍历,发现11>7,那么再从7开始寻找,寻找比11大的数为止(比11大的数不放入集合内),如果找到数列末尾,则结束,将这些数记作受影响的数的集合,记该集合最大值为a
记11的位置为index,那么从index-1的位置开始与a比较,大于a的数则放入与11相同的集合,也就是分歧数的集合中(在这里应将10放入)
如果没有到末尾则按这样的方法继续查找......
按以上的数列,合并两个集合可以得到{10,11,7,8,9},则该数列中的数为顺序不同的数

泛泛之交 2017-09-14 6 楼

先确认位置不对的情况,有2种情况
1.n位置的值比n-1,n+1位置的值都小
2.n位置的值比n-1,n+1位置的值都大
然后遍历数组找出满足这些条件的值的位置

灵芸 2017-08-18 5 楼

如果这两个数字越靠后,需要查找的次数就越多,以下是我的代码,不知道有没有更好的方法。

 $arr = array();
for($i=0;$i<100;$i++){
$arr[$i]=$i;
}
$arr[59] = 200;
$arr[87] = 150;

$count = count($arr);
$pre_wrong = -1;
$end_wrong = -1;
$c = 0;
for($i=0;$i<$count;$i++){
if($pre_wrong==-1)
if($arr[$i]>$arr[$i+1]){
$pre_wrong=$i;
$i+=2;
}
if($end_wrong==-1)
if($arr[$i]<$arr[$i-1])
$end_wrong = $i-1;
$c++;
if($pre_wrong!=-1 && $end_wrong!=-1) break;
}
var_dump($pre_wrong,$end_wrong,$c); //$c为查找的次数

结果:
int(59) int(87) int(87)
位置1 位置2 查找次数

瑾兮 2017-08-17 4 楼

代码很粗糙,应该有要优化的地方。

function getWrongNum(int[] arr){
int arr_counter = count(arr);
int pre_wrong_num = -1;
int end_wrong_num = -1;
for(int i=0; i<arr_counter/2+1; i++){
if(pre_wrong_num == -1)
if(arr[i]>arr[i+1])
pre_wrong_num = i;
if(end_wrong_num = -1)
if(arr[i]<arr[i-1])
end_wrong_num = i;
}
int[] result = {pre_wrong_num, end_wrong_num};
return result;
}

想挽留 2017-08-15 3 楼

1 2 3 5 4 6
在这里我认为只有一个错,且是数据“5”的位置错

下面是我的算法:

int get_wrong_num(int arr[], int len, int wrong_index_arr[])
//arr传入的是所要测试的数组,len是数组长度,wrong_index_arr是存放错误位置的标号
{
int i = 0;
int k = 0;

if (arr[0] > arr[1])
{
if (arr[1] < arr[2])
{
wrong_index_arr[k++] = 0;
}
else
{
wrong_index_arr[k++] = 1;
}
}
i = 1;
while ((i < len - 1) && (k < WRONGSIZ)) /*这里设置了一个宏WRONGSIZ 其值这里为2*/
{
if (arr[i] > arr[i+1])
{
if (arr[i+1] > arr[i-1])
{
wrong_index_arr[k++] = i;
}
else
{
wrong_index_arr[k++] = i + 1;
}
i++;
}
i++;
}
if (k < WRONGSIZ)
{
wrong_index_arr[k] = wrong_index_arr[k-1];
wrong_index_arr[k-1] = wrong_index_arr[k-1]-1;
}

return 0;
}

甜柠檬 2017-08-04 2 楼

从2到100.每个2开始比对前一个和后一个是否比2n大和小。

归属感 2017-07-07 1 楼

不能使用二分法 跳段了就悲剧了 只能乖乖遍历 老实说不知道在玩什么

 arr = {11,22,33,44,55,66,44,12,1024}; //如果超过2个 则new 一个ArrayList保留结果 不断刷新first的值
int first = -1 ,second;
for(int i = 0 ; first < arr.length() ; i++ )
{
if(arr[i] <= arr[i+1]) continue;
else
{
first = i;
if(first==-1) second = first;
continue;
}
}

int temp = first;
first = second;
second = temp; #done