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

Question

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

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

Например:

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

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

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

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

В Python (т является numpy.array) это может быть:

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

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

Answer 1

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

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

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

Answer 2

Простой метод (с 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); 

Answer 3

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

Answer 4

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

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

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

Answer 5

Это 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 6

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

Answer 7

Вот способ сделать это в O (журнал 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]