Проблема с функцией массива

Question

Допустим, у меня есть возрастающая последовательность целых чисел: seq = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 4 ...] не гарантированно иметь одинаковое число каждое целое число, но гарантированно увеличивается на 1.

Есть ли функция F, которая может работать с этой последовательностью, при которой F (seq, x) выдаст мне все 1, когда целое число в последовательности равно x, а все остальные целые числа будут равны 0.

Например:

t = [1, 1, 1, 1, 2, 2, 3, 3, 3, 4]

F (t, 2) = [0, 0, 0, 0, 1, 1, 0, 0, 0, 0]

РЕДАКТИРОВАТЬ: Я, вероятно, должен был сделать это более ясным. Есть ли решение, в котором я могу выполнить некоторые алгебраические операции над всем массивом, чтобы получить желаемый результат, не повторяя его?

Итак, мне интересно, могу ли я сделать что-то вроде: F (t, x) = t op x?

В Python (t это numpy.array) это может быть:

(т * -1)% х или что-то ...

EDIT2: я обнаружил, что тождественная функция I (t [i] == x) приемлема для использования в качестве алгебраической операции. Извините, я не знал о функциях идентификации.

Answer 1

Существует очень простое решение, которое не требует большинства ограничений, которые вы накладываете на домен. Просто создайте новый массив того же размера, выполните цикл и проверьте равенство между элементом в массиве и значением, с которым вы хотите сравнить. Когда они одинаковы, установите соответствующий элемент в новом массиве равным 1. В противном случае установите его равным 0. Фактическая реализация зависит от языка, с которым вы работаете, но должна быть довольно простой.

Если мы учтем ваш домен, вы можете внести пару оптимизаций. Если вы начинаете с массива нулей, вам нужно только заполнить их. Вы знаете, что вам не нужно начинать проверку, пока (n - 1) th элемент, где n - это значение, с которым вы сравниваете, потому что должно быть хотя бы одно из чисел от 1 до n при увеличении порядок. Если вам не нужно начинать с 1, вы все равно можете начать с (n - start). Точно так же, если вы не сталкивались с этим на array[n - 1], вы можете прыгнуть на n - array[n - 1] больше элементов. Вы можете повторить это, пропуская большинство элементов столько, сколько вам нужно, пока вы не достигнете правильного значения или конца списка (если его там вообще нет).

После того, как вы закончите работать с нужным значением, вам не нужно проверять оставшуюся часть массива, поскольку вы знаете, что он всегда будет увеличиваться. Так что ты тоже можешь остановиться рано.

Answer 2

Вот способ сделать это в O (log n)

>>> from bisect import bisect
>>> def f(t, n):
...     i = bisect(t,n-1)
...     j = bisect(t,n,lo=i) - i
...     return [0]*i+[1]*j+[0]*(len(t)-j-i)
...         
... 
>>> t = [1, 1, 1, 1, 2, 2, 3, 3, 3, 4]
>>> print f(t, 2)
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0]

Answer 3

Я бы инициализировал массив нулей, затем выполнил бы бинарный поиск по последовательности, чтобы найти первый элемент, который соответствует вашим критериям, и только с этого начинал бы устанавливать 1.Как только у вас будет неравное состояние, остановитесь.

Answer 4

Вот метод Java, который возвращает новый массив.

public static int[] sequence(int[] seq, int number)
{
    int[] newSequence = new int[seq.length];

    for ( int index = 0; index < seq.length; index++ )
    {
        if ( seq[index] == number )
        {
            newSequence[index] = 1;
        }
        else
        {
            newSequence[index] = 0;
        }
    }

    return newSequence;
}

Answer 5

Вы запрашиваете готовый C ++, Java API или алгоритм? Или это домашнее задание?

Я вижу простой алгоритм сканирования массива от начала до конца и сравнения с каждым. Если равно, тогда положить как 1, иначе как 0. В любом случае, чтобы поместить элементы в массив, вам нужно будет получить доступ к каждому элементу нового массива, по крайней мере, один. Таким образом, общий подход будет O (1).

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

Answer 6

A алгоритм дихотомии может быстро найти диапазон, в котором t[x] = n делает такую ​​функцию сублинейной сложности во времени.

Answer 7

Простой метод (с кодом C #) состоит в том, чтобы просто выполнить итерацию последовательности и проверить ее, возвращая либо 1, либо 0.

foreach (int element in sequence)
   if (element == myValue)
       yield return 1;
   else 
       yield return 0;

(записано с использованием LINQ)

sequence.Select(elem => elem == myValue ? 1 : 0);