3

Задан массив a0,a1,…,an−1. Для каждого элемента найдите расстояние от него до ближайшего нуля. Гарантируется, что в массиве встречается ноль хотя бы один раз.

Входные данные В первой строке входных данных содержится целое число n (1≤n≤2⋅10^5) — длина массива a. Вторая строка содержит элементы массива, записанные через пробел (−10^9≤ai≤10^9).

Выходные данные Выведите последовательность d0,d1,…,dn−1. Значение di должно быть равно расстоянию от элемента в позиции i до ближайшего элемента, равного нулю.

Примеры

входные данные

9
2 1 0 3 0 0 3 2 4

выходные данные
2 1 0 1 0 0 1 2 3 

входные данные

5
0 1 2 3 4

выходные данные
0 1 2 3 4 

входные данные
7
5 6 0 1 -2 3 4
выходные данные
2 1 0 1 2 3 4 

Код:

n=int(input())
a=list(map(int, input().split()))
for i in range(len(a)):
    if a[i]!=0:
        b=[list(reversed(a[:i + 1])), a[i:]]
        left=b[0].index(0) if 0 in b[0] else len(a)
        right=b[1].index(0) if 0 in b[1] else len(a)
        a[i]=min(left,right)
print(*a)

Данный код не проходит по времени на 39 тесте. Как его ускорить? Или может быть он неправильный?

4
  • У вас в примерах входные данные длиннее, чем выходные - а по условию должны быть одинаковы...
    – Harry
    2 янв 2020 в 13:23
  • @Harry там форматирование было кривое 2 янв 2020 в 13:27
  • А как это исправить?
    – wargas
    2 янв 2020 в 13:31
  • переменная n дана, чтобы не использовать каждый раз len(a). И вы создаете n списков, без которых можно обойтись. 2 янв 2020 в 13:46

6 ответов 6

5

Как обычно, ощущение, что у вас O(n2).

Увы, я не знаю python, но если вас натолкнет на мысли решение на C++...

int main(int argc, const char * argv[])
{
    int n;
    cin >> n;
    vector<int> d(n), zeros;

    int l = 2000000;
    zeros.push_back(-1);
    for(int v, i = 0; i < n; ++i)
    {
        cin >> v;
        if (v == 0)
        {
            zeros.push_back(i);
            l = 0;
        }
        d[i] = l++;
    }

    for(int i = 1; i < zeros.size(); ++i)
    {
        int b = zeros[i-1];
        int e = zeros[i];
        for(int j = e-1; j > b; --j)
        {
            if (d[j] > e-j) d[j] = e-j; else break;
        }
    }
    for(int x: d) cout << x << " "; cout << endl;
}

Смысл примерно - сначала читаем и отмечаем все нули и вправо от нуля пишем расстояние от последнего считанного нуля.

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

Самые левые элементы заполняем фейковым значением, заведопо превосходящим n.

4
  • Лично я бы делал в 1 проход, используя факт, что ровно половина раности уходит к левому 0, остальное в правому. Главное концы не потерять. Для генерации ответа достаточно знать только позицию предыдущего 0.
    – pavel
    2 янв 2020 в 16:19
  • @pavel Ну все равно ведь - достигнув правого 0, идти надо будет влево, нет?
    – Harry
    2 янв 2020 в 17:02
  • 1
    А зачем? Позицию левого мы знаем, сами числа нас не интересуют. А вывести 1 2 3 4 ... (cur-prev)/2 ... 3 2 1 и так можно)
    – pavel
    2 янв 2020 в 18:15
  • 1
    @pavel Ну... вообще-то да. Можно и не строить... Только когда я о чем-то таком думал, мне показалось, что код будет существенно объемнее...
    – Harry
    2 янв 2020 в 18:30
3

я бы сделал так:

import numpy as np

def func(lst):
    lst=np.array(list(map(int, lst.split())))
    zeros = np.where(lst==0)[0]
    for i in np.nonzero(lst)[0]:
        lst[i] = min(np.abs(i-zeros))
    return lst.tolist()

Тесты:

print(func('0 2 1 0 3 0 0 3 2 4'))
print(func('2 1 0 3 0 0 3 2 4'))
print(func('0 1 2 3 4'))
print(func('5 6 0 1 -2 3 4'))

Вывод:

[0, 1, 1, 0, 1, 0, 0, 1, 2, 3]
[2, 1, 0, 1, 0, 0, 1, 2, 3]
[0, 1, 2, 3, 4]
[2, 1, 0, 1, 2, 3, 4]
4
  • No module named 'numpy' пишет...
    – wargas
    4 янв 2020 в 8:16
  • Значит, его нужно установить. pip install numpy, например
    – strawdog
    4 янв 2020 в 8:18
  • invalid syntax пишет
    – wargas
    5 янв 2020 в 9:19
  • Учитель сказала сделать без numpy и без enumerate, но, к сожалению, я не могу понять, как это сделать...
    – wargas
    12 янв 2020 в 14:35
0
n= int(input())
a = input().split()
fwd = []
bwd = []
for i in range(n):
    a[i] = int(a[i])
    if a[i] == 0:
        fwd.append(i)
bwd = fwd[::-1]
for i in range(n):
    bw = min(abs(i - fwd[0]), abs(i - bwd[-1]))
    if a[i] == 0:
        if len(fwd) > 1:
            fwd.pop(0)
            bwd.pop()
    a[i] = bw
    print(bw, end=" ")

1
  • Саша Новожилов, на 19 тесте, к сожалению, не проходит
    – wargas
    15 янв 2020 в 15:43
0

Верный код такой, но выполняется больше 3 сек.:

n = 9
a = [2, 5, 0, 7, 2, 3, 0, 6, 0]
a_rev = list(reversed(a))

fwd = []
bwd = []
for i in range(n):
    if a[i] == 0:
        fwd.append(i)
    if a_rev[i] == 0:
        bwd.append(i)
for i in range(n):
    bw = abs(i - fwd[0])
    fw = abs(i - bwd[0])
    if a[i] == 0:
        if len(fwd) > 1:
            fwd.pop(0)
    if a_rev[i] == 0:
        if len(bwd) > 1:
            bwd.pop(0)
    a[i] = bw
    a_rev[i] = fw
a_rev = a_rev[::-1]
rezult_dist = [min(f, b) for f, b in zip(a, a_rev)]
result_list_string = [str(i) for i in rezult_dist]
result_string = ' '.join(result_list_string)
# вывод в терминал
print(result_string)

Вывод:

2 1 0 1 2 1 0 1 0

1
  • добро пожаловать на Stack Overflow на русском! пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав править 28 сен 2021 в 11:51
0

Время выполнения : 2.09s

    def distance_one_way(house_list):
            last_null = -1
            one_way_list = [0] * n
            for null_number in range(0, n):
                if house_list[null_number] == '0':
                    for house_number in range(last_null + 1, null_number):
                        one_way_list[house_number] = abs(house_number-null_number)
                    last_null = int(null_number)
            if last_null < n:
                for house_number in range(last_null+1, n):
                    one_way_list[house_number] = float("inf")
            return one_way_list
        
        
        def distance_two_way(house_list):
            forward = distance_one_way(house_list)
            backward = distance_one_way(house_list[::-1])
            final_list = [min(forward_dist, back_dist)
                          for forward_dist, back_dist in zip(forward, backward[::-1])]
            final_list = [str(distance) for distance in final_list]
            return final_list
        
        
        if __name__ == '__main__':
            n = int(input())
            house_list = list(input().split())
            print(" ".join(distance_two_way(house_list)))
0

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

... решение из разряда ненормального программирования. Задачу можно решить за линейное время (что не новость) и в памяти пропорциональной логарифму расстояния между соседними нулями (это новинка).

Чтобы удовлетворить жестким ограничениям по памяти пришлось отказаться от чтения входных данных через input() (сразу линейная память!). Чтение сделано посимвольно, счётчик чисел пропускается, сами числа не анализируются целиком - проверяется лишь только первый символ. В памяти хранится только расстояние до последнего встреченного нуля. В печати пришлось отказаться от print(*...) чтобы сократить требования к памяти:

import sys


# пропускает пробелы
# возвращает первый непробел или пустую строку если файл кончился
def skip_spaces():
    c = ' '
    # выйти если файл кончился или прочитан нeпробел
    while c.isspace():
        c = sys.stdin.read(1)
    return c


# пропускает непробелы
# возвращает первый пробел или пустую строку если файл кончился
def skip_nonspaces():
    c = '_' # или любой непробел
    # выйти если файл кончился или прочитан пробел
    while c != '' and not c.isspace():
        c = sys.stdin.read(1)
    return c


# читает числа из файла, выдаёт флаги вида "это ноль"
# по числу прочитанных чисел
def read_zeros():
    while True:
        # пропустить пробельные символы
        c = skip_spaces()
        if c == '': # признак конца файла
            break

        # ноль - единственное число начинающееся с символа '0'
        yield c == '0'

        # пропустить все символы до пробела или конца файла
        if skip_nonspaces() == '': # признак конца файла
            break


# решает задачу: читает числа, выводит расстояния до ближайшего нуля
def dists():
    first = True
    k = 0 # эта переменная отвечает за логарифмическую память
    for z in read_zeros():
        if z:
            if first:
                yield from range(k, 0, -1) # первый спуск
                first = False
            else:
                h = k // 2
                yield from range(h + 1)            # подъём на холм
                yield from range(k - h - 1, 0, -1) # спуск с холма
            k = 0
        k += 1
    yield from range(k) # последний подъём


def main():
    # пропустить n
    skip_spaces()
    skip_nonspaces()

    first = True
    for d in dists():
        if first:
            first = False
            print(d, end='') # просто число
        else:
            print('', d, end='') # пробел и число
    print()


main()

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.