我有一个长度为10的数组，其中填充了0-9的数字。
这些数字大部分是按顺序排列的。但是起始索引处的数字可以是任何数字，并且不知道数字是按升序还是降序排列的（一旦达到最小/最大数字，数字将绕回 - 例如，当它达到9时，0变成最小数字，反之亦然）。
恰好有一个数字不按顺序排列（好像被拔出来并随机插入到数组中一样）。
示例：
[4, 3, 1, 0, 9, 8, 7, 2, 6, 5]
索引7处的数字2是无序的。索引1和2之间的数字“间隙”是可以接受的，数字3或1都不被视为无序。
如何最好地确定无序数字的索引？
更多示例 - 不在正确位置上的数字用*标记：
[2, 3, *0, 4, 5, 6, 7, 8, 9, 1]
[5, 6, 7, 9, *8, 0, 1, 2, 3, 4]
[7, 6, 5, 4, 3, *8, 2, 1, 0, 9]
[0, *5, 1, 2, 3, 4, 6, 7, 8, 9]
[4, 3, *0, 2, 1, 9, 8, 7, 6, 5]
{1,2,3,4000,5,6,7}，您不能只查看 1,3,5,7 并说一切都很好。 - Seph[0,1,2,3,5,4,6,7,8,9]，我认为将此附加到算法中应该就可以了 - "如果没有发现任何数字排序错误，则选择与**任一邻居**具有差异不等于1或n-1的任一数字"。对于[4,3,1,0,9,8,7,2,6,5]，1和0之间的差为1，因此都不会被选中，而会选择2。 - Bernhard Barker查看每个其他元素，并计算它们之间的差异。
如果大多数差异是正数，则顺序是升序。如果大多数是负数，则为降序；可以像处理另一种情况一样准确地判断，我不会进一步讨论它。
当然，您需要循环并计算第（N-1）个和第0个元素之间的差异，或者其他任何元素。
从现在开始，考虑到差异对N取模的结果。
如果差值为2，则这是没有额外或缺少元素的常规情况；请忽略它。
如果差值为3，则可能有一个元素在这附近被删除了。但我们要寻找的是其新位置，而不是旧位置；因此也要忽略这种情况。
如果差值为1，则乱序的元素位于这些数字之间。
如果还有其他差异，则必须有两个相邻的差异。导致这两个差异的元素即为乱序元素。
在两个连续数字交换的情况下，可以选择其中一个认为是乱序元素。所产生的差异将是相邻的（1,3）或（3,1）。该方法会选择两个可能的答案之一。
对于所讨论的数组：
array -> 2 3 0 4 5 6 7 8 9 1(2)
\ / \ / \ / \ / \ /
diffs -> -2 5 2 2 -7(=3 mod 10)
*
为了节省空间，在后面的例子中我将不再注明模10相等的情况。
array -> 5 6 7 9 8 0 1 2 3 4(5)
\ / \ / \ / \ / \ /
diffs -> 2 1 3 2 2
*
array -> 7 6 5 4 3 8 2 1 0 9(7)
\ / \ / \ / \ / \ /
diffs -> -2 -2 -1 -2 -3
*
array -> 0 5 1 2 3 4 6 7 8 9(0)
\ / \ / \ / \ / \ /
diffs -> 1 2 3 2 2
*
array -> 4 3 0 2 1 9 8 7 6 5(4)
\ / \ / \ / \ / \ /
diffs -> -4 -9 -3 -2 -2
*
array -> 0 2 1 3 4 5 6 7 8 9(0) swapped adjacent elements, case 1
\ / \ / \ / \ / \ /
diffs -> 1 3 2 2 2
*
array -> 0 1 3 2 4 5 6 7 8 9(0) swapped adjacent elements, case 2
\ / \ / \ / \ / \ /
diffs -> 3 1 2 2 2
*
array -> 0 2 3 4 5 6 7 1 8 9(0) element removed and inserted at odd pos
\ / \ / \ / \ / \ /
diffs -> 3 2 2 1 2
*
array -> 0 2 3 4 5 6 1 7 8 9(0) element removed and inserted at even pos
\ / \ / \ / \ / \ /
diffs -> 3 2 6 7 2
*
array -> 0 7 1 2 3 4 5 6 8 9(0) element removed and inserted at odd pos
\ / \ / \ / \ / \ /
diffs -> 1 2 2 3 2
*
array -> 0 1 7 2 3 4 5 6 8 9(0) element removed and inserted at even pos
\ / \ / \ / \ / \ /
diffs -> 7 6 2 3 2
*
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 // first item move to end
2, 1, 3, 4, 5, 6, 7, 8, 9, 0 // adjacent items swapped
对于其他所有情况，幸运的是，“顺序不对”的项目将与其邻居同时相隔超过1个位置（因为上述#2原因）。
for (i = 0; i < arr.length; i++) {
int priorIndex = (i-1) % arr.length;
int nextIndex = (i+1) % arr.length;
int diffToPriorValue = abs(arr[i] - arr[priorIndex]);
int diffToNextValue = abs(arr[i] - arr[nextIndex]);
if (diffToPriorValue > arr.length/2)
diffToPriorValue = arr.length - diffToPriorValue; // wrap-around
if (diffToNextValue > arr.length/2)
diffToNextValue = arr.length - diffToNextValue; // wrap-around
if (diffToPriorValue != 1 && diffToNextValue != 1)
return i;
return -1;
首先，我将从定义“out of order”开始：
Suppose we have a list of numbers A
If there exist A[i] in A,
Such that A[i-1] <= A[i] <= A[i+1], then A[i] is "in order"
Otherwise, A[i] is "out of order"
算法:
FOR i: 1..SIZE(A) DO
PRINT " "
PRINT A[i]
IF A[i-1] <= A[i] <= A[i+1]
THEN
CONTINUE
ELSE
PRINT "*"
REMOVE A[i]
END-IF
END-FOR
测试:
INPUT: { 2, 3, 0, 1, 2, 3, 5, 6, 7, 8, 9, 1 }
OUTPUT: { 2, 3, 3, 5, 6, 7, 8, 9 }
CONSOLE: 2 3 0* 1* 2* 3 5 6 7 8 9 1*
A[i-1] <= A[i] <= A[i+1] 是不行的。<=，可以只是 <。0,1,2,3,4,8,5,6,7,9，你的算法会标记 8 和 5，而不是只有 8。0，1，2，3，4，8，5，6，7，9，我的算法仅会标记8，因为当8被标记时，它将从列表中删除（忽略）。感谢您对我的算法感兴趣，如果您讨厌全大写字母，那是我们在编写伪代码算法时使用的方式。6,7,8,9,0,1,2,3,4,5 - 序列从中间某处开始，一旦到达末尾，它就会从开头继续。我看过（并编写过）大量伪代码，但从未全部使用大写字母，但由于没有标准，我想任何人都可以按照自己的方式进行。 - Bernhard Barker9 和 0 被认为是相邻元素。# checks if two given numbers are adjacent or not, independent of wrapping
def adjacent?(a, b)
(a - b).abs == 1 || [a, b].sort == [0, 9]
end
# finds the misplaced number in a list
def misplaced_number(list)
middle_index = 1
(list + list).each_cons(3).find { |first, second, third|
adjacent?(first, third)
}[middle_index]
end
以下是进行的测试。第二个和最后一个测试失败，因为存在歧义。
test([2, 3, 0, 4, 5, 6, 7, 8, 9, 1], 0)
test([5, 6, 7, 9, 8, 0, 1, 2, 3, 4], 8) # [FAIL: result = 9]
test([7, 6, 5, 4, 3, 8, 2, 1, 0, 9], 8)
test([0, 5, 1, 2, 3, 4, 6, 7, 8, 9], 5)
test([4, 3, 0, 2, 1, 9, 8, 7, 6, 5], 0)
test([2, 4, 5, 6, 7, 8, 9, 0, 1, 3], 2) # [FAIL: result = 3]
def test(list, expected)
result = misplaced_number(list)
assert result == expected_value, "Got #{result} but expected #{expected} from list #{list}"
end
因此，将srikanta和n.m.在Haskell中组合：
import Data.List (findIndex)
f s = maybe (-1) (+1) . findIndex (==1)
$ zipWith (\a b -> abs (a - b)) s (drop 2 s ++ take 2 s)
*Main> f [2,3,0,4,5,6,7,8,9,1]
2
*Main> f [5,6,7,9,8,0,1,2,3,4]
3
...
#include <stdio.h>
int main(void)
{
int array[10] = { 4, 3, 1, 0, 9, 8, 7, 2, 6, 5};
size_t idx;
int diff, state,this,next;
#define COUNT (sizeof array/sizeof array[0])
#define FOLD(n,i) ((i)%(n))
#define FETCH(a,i) a[FOLD(COUNT,(i))]
this = FETCH(array,COUNT-1);
next = FETCH(array,0);
diff = next - this;
state = (diff < -1 || diff >1) ? 1: 0;
for (idx = 0; idx < COUNT; idx++) {
this = next;
next = FETCH(array,idx+1);
diff = next - this;
state = (state<<1) & 3;
state |= (diff < -1 || diff >1) ? 1: 0;
if (state==3) putc('*', stdout);
printf("%d ", this );
}
putc('\n', stdout);
return 0;
}
输出：
4 3 1 0 9 8 7 *2 6 5
int element, backdiff, forwarddiff;
boolean elementFound = false;
if(abs(a[0] - a[1]) == 2 )
return "Out of Order Element is @ position" + (a[0] - a[1] > 0 ? 0 : 1);
for (i=1;i<n;i++){
if(!elementFound){
backdiff = abs(a[i-1] - a[i]);
forwarddiff = abs(a[i+1] - a[i]);
if( (backdiff == 1 && forwarddiff == 1) ||
(backdiff == n-1 && forwarddiff == 1) ||
(backdiff == 1 && forwarddiff == n-1) )
continue;
if(forwarddiff == 2 || backdiff == 2)
element = abs(a[i]-(a[i-1]+a[i+1]));
elementFound = true;
if(forwarddiff > 2 || backdiff > 2)
return "Out of Order Element is @ position" + (forwarddiff > 2 ? (i+1) : i);
} else {
if(a[i] == element)
return "Out of Order Element is @ position" + (i);
}
}
[1, 9, 2, 0, 3, 8, 4, 7, 5, 6]，根据这些规则，你会说哪个数字是错位的？它们都有多个间隔，并且它们都环绕着。 - Anurag