Лучший способ найти число в массиве, который "вышел из строя"?

Ответ 1

Чтобы найти номер, который не соответствует порядку, вы смотрите на каждый элемент массива. Итак, вам нужно перебрать весь массив со сложностью O (n).

Когда вы зацикливаете массив, вы должны

• вычислить абсолютное значение разницы между предыдущим номером и текущим номером.
• вычислить абсолютное значение разницы между текущим номером и следующим числом

Если оба вышеперечисленных различия больше 1 и не равны n-1 (когда разница равна n-1, это точка, где ваш массив переворачивается), то это номер, который не соответствует порядку.

Ответ 2

Посмотрите на каждый другой элемент и вычислите различия.

Если большинство различий положительны, порядок возрастает. Если большинство отрицательно, оно спускается; его можно решить точно так же, как и в другом случае, и я не буду рассматривать его дальше.

Конечно, вам нужно обернуть и вычислить разницу между (N-1) th и 0-м элементом или что-то еще.

Отныне посмотрите на diffs modulo N.

Если diff равен 2, это обычный случай отсутствия лишних или отсутствующих элементов; игнорировать его.

Если значение diff равно 3, элемент где-то здесь дергается. Но мы не ищем своего старого места, мы ищем его новое место; игнорируйте это тоже.

Если diff равен 1, то элемент вне порядка находится между этими числами.

Если у вас есть другой diff, тогда у вас должно быть два из них рядом друг с другом. Элемент out of order - тот, который производит оба этих различия.

В случае смены двух последовательных номеров один из них может считаться неработоспособным. Полученные различия будут либо (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)
             *

В следующих примерах я не буду указывать равенство mod 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
             *

Ответ 3

Следующие надуманные примеры не имеют уникального решения. Вам нужно решить, что происходит в этих случаях:

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;

Ответ 4

Сначала я начну с определения того, что "не в порядке":

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

TEST

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*

Ответ 5

Здесь решение похоже на Халида.

Два элемента считаются смежными, если они могут появляться рядом друг с другом, не знающими обертывания. Таким образом, 9 и 0 считаются смежными элементами.

Алгоритм циклически проходит через каждый набор из трех последовательных элементов и проверяет, является ли первый и третий соседними или нет. Если они смежны, то среднее значение должно быть не в порядке.

Я присоединяюсь к данному списку к себе, создавая таким образом массив размером 20. Это касается особого случая, когда число было перемещено в начало или конец списка.

# 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

Ответ 6

Таким образом, объединение 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
...

Ответ 7

#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

Ответ 8

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);
    }   
}