0

Мне нужно найти количество элементов в массиве, разность которых больше k. Например для массива [1,3,5,8] и k = 4, таких элементов будет 2(8-1 и 8-3). Гарантируется, что массив отсортирован. Нужно решить задачу за O(n)(линейная сложность).

n,k = map(int,input().split()) #n - длина массива
a = list(map(int,input().split()))# сам массив

i = 0
j = 1
rez = 0
if a[j] - a[i] > k:
    j += 1
    rez += 1
go = True
while go:
    if j != n: 
        if a[j] - a[i] > k:
            rez += 1
        j += 1
    elif j == n:
        if i != n-1:
            i += 1
            j = i+1
        else:
            go = False
    if i == n:
        go = False
print(rez)

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

Ссылка на задачу - https://informatics.mccme.ru/mod/statements/view3.php?id=40319&chapterid=111975#1

2
  • "алгоритм точно не линейный" - как узнали?
    – user176262
    3 июл 2020 в 17:12
  • Посчитал сколько проходов сделает мой цикл в худшем случае. В первый раз он будет сравнивать n случаев, во второй n-1, пока не дойдёт до n - n-1. Если вынести общий множитель и посчитать, то линейно сложности не будет. Плюс в тестах пишет, что превышено время работы
    – Maksim
    3 июл 2020 в 17:19

1 ответ 1

2

Левый индекс идёт по одному шагу. Правый индекс находит минимальный элемент, удовлетворяющий условию. Значит, от правого индекса до конца есть n-r годных пар с элементом по левому индексу. Каждый индекс по разу проходит диапазон, сложность линейная

r = 0
res = 0
for l in range(n - 1):
    while (r < n) and (a[r] - a[l] <= k):
        r += 1
    res += n - r
    if r == n:
        break
print(res)

Ваш ответ

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

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