Протестируйте ряд чисел, чтобы убедиться, что они соответствуют последовательности 1,2,3 ... n - PullRequest
Новая
       18

Протестируйте ряд чисел, чтобы убедиться, что они соответствуют последовательности 1,2,3 ... n

0 голосов
/ 22 июня 2011

Я пытаюсь найти немного более элегантное решение, чтобы найти, если последовательность чисел в порядке. Это для веб-формы, и я даю пользователю возможность нумеровать элементы, и это позволит настроить порядок. Я знаю максимальное количество предметов, и оно всегда должно начинаться с одного.

Прямо сейчас (я знаю, что это не правильно) Я проверяю, чтобы убедиться, что все числа разные, и складываю то, что должно (например, для трех тестируемых предметов это добавляет к 6). У кого-нибудь есть лучшее / более точное (так как можно сломать мое) решение? Я использую php, но мне действительно нужна логика, чтобы ваш пример мог быть в псевдокоде или на любом относительно легком для чтения языке.

Ответы [ 3 ]

2 голосов
/ 22 июня 2011

Поскольку вы знаете максимальное количество элементов, вы можете избежать сортировки, просто выделив логический массив и заполнив его.В псевдокоде: 

define numsInOneThruN (int xarr[], int sz):
    # Declare the boolean array and initialise to all false.

    declare isSet[1..sz]
    for all i in 1..sz:
        isSet[i] = false

    # For every number in list, if within range, set boolean value to true.

    for all i in xarr:
        if i >= 1 and i <= sz:
            isSet[i] = true

    # Check that all boolean values are true.

    for all i in 1..sz:
        if not isSet[i]:
            return false

    return true

Это имеет преимущество в том, что O(n) сложность времени, а не в лучшем случае O(n log n) - это, вероятно, не будет иметь значения для небольших наборов данных, но может стать важнымдля большего.

Следует также учитывать тот факт, что это имеет более высокую сложность пространства, чем сортировка на месте, так как она использует массив, равный размеру ввода.Это делает его O(n) пробелом вместо O(1) для опции сортировки.

Как всегда, вы обычно можете обменять пространство на время в зависимости от ваших потребностей.

2 голосов
/ 22 июня 2011

Просто отсортируйте введенные пользователем числа и посмотрите, соответствуют ли они индексу, который вы увеличиваете на 1. 

nMax = 10
sortedUserArray = Sort(UserArray)

For i = 1 To nMax
    If Not sortedUserArray(i) = i Then
        ' Input not valid. 
        ' Throw an error or something. 
    End If
Next i

Для части Sort существует множество алгоритмов сортировки: Быстрая сортировка , Прямая вставка , Heapsort и т. Д. Просто выберите тот, который подходит ваши потребности и выполните поиск, чтобы найти готовую процедуру в Интернете. У вашего языка выбора могут быть даже встроенные алгоритмы сортировки, поэтому вам даже не нужно заглядывать так далеко.

1 голос
/ 22 июня 2011

Если вы уже установили, что все числа разные, просто проверьте минимальное и максимальное значения.Есть только n различных чисел, которые удовлетворяют 1 <= x <= n. </p>

...