Алгоритм пропуска числа?

Question

[Dauren S]

В сервисе Киношечка зарегистрировано n пользователей. Все пользователи, за исключением двух, в последние два месяца посещали сайт. Нужно определить id пользователей, которые сайт не посещали.
Формат ввода
Первая строка содержит число n — количество зарегистрированных пользователей. Это целое число в диапазоне от 2 до
10 в 6 степени.
Во второй строке через пробел заданы различные n - 2 целых числа. Каждое из них не превосходит n и больше нуля.

Формат вывода
Нужно в одной строке вывести по возрастанию два пропущенных числа, разделённые пробелом.
Я решил так
Файл input.txt содержит

19
16 11 5 7 15 18 6 13 9 10 14 12 2 19 4 17 3

Файл main.py

with open('input.txt', 'r') as f:
    nums = f.read().splitlines()
    all_count=nums[0]
    rows=nums[1:]
    result_string=''
    for r in rows:
        arr=list(map(int, r.split()))
    arr.sort()
    for i in range(1, int(all_count)+1):
        if i not in arr:
            result_string+= str(i) +' ' 
    print(result_string)

Отрабатывает верно, но на 7 тесте не проходит так как время исполнения больше 7 секунд, а данных в input.txt очень много.
Как можно оптимизировать алгорит?

Answer 1

[zexer]

n = 19
numbers_as_string = '16 11 5 7 15 18 6 13 9 10 14 12 2 19 4 17 3'
numbers = [int(i) for i in numbers_as_string.split(' ')]

all_numbers = set(range(1, n + 1))
numbers = set(numbers)
sorted_diff = [str(i) for i in sorted(all_numbers.difference(numbers))]
print(' '.join(sorted_diff))

Comments

[aRegius]

Только в range крайний предел n+1

[zexer]

aRegius, да, вы правы.

[aRegius]

zexer, Вы добавили строку:

sorted_diff = [str(i) for i in sorted(all_numbers.difference(numbers))]

На вкус и цвет, как говорится ) Но выражение str(i) for i in ... можно использовать прямо в join:

' '.join(str(i) for i in sorted(all_numbers.difference(numbers)))

Answer 2

[Stalker_RED]

n = 19
visitors = '16 11 5 7 15 18 6 13 9 10 14 12 2 19 4 17 3'.split(' ')
missed = list(filter(lambda x: str(x) not in visitors, range(1, n+1)))

https://ideone.com/PxuDHE

Comments

[Dauren S]

Работает но время исполнения
6 test time-limit-exceeded 7.524s / 3.74Mb

with open('input.txt', 'r') as f:
    nums = f.read().splitlines()
    n=int(nums[0])
    rows=nums[1:]
    missed=''
    for r in rows:
        missed= list(filter(lambda x: str(x) not in r.split(' '), range(1, n+1)))
    print(' '.join(map(str, missed)))

[Stalker_RED]

Dauren S, это с codewars задачка? :)
видимо нужно искать способы пооптимальнее, чем O(n²)

К примеру предварительно отсортировать массив и затем перебрать сравнивая соседние элементы. Где разница больше единицы - там и оно.

Answer 3

[Wataru]

Это обобщение известной задачи, где пропущено одно число. Там можно, например, вычесть все числа из n(n+1)/2. Или про-xor-ить все числа от 1 до n и все числа в массиве.

Для двух чисел нужно составить какие-то 2 уравнения, Например, найдите сумму двух чисел и сумму их квадратов: Сумма пропущенных чисел - это n*(n+1)/2 - (сумма всех чисел в массиве). Здесь надо аккуратно не забыть о возможном переполнении (если ваш язык, например, С++). Сумма квадратов: сумма квадратов всех чисел от 1 до n минус квадраты всех чисел в массиве.

Итак, вы за O(n) двумя не вложенными циклами (один для суммы квадратов 1..n, другой для обработки всех чисел массива) нашли X+Y=A и X^2 + Y^2=B.

Теперь решите уравнения относительно X и Y: Выразите X через Y из первого уравнения и подставьте во второе. Решите квадратное уравнение и получите:
X = (A-sqrt(2B-A^2))/2, Y = (A+sqrt(2B-A^2))/2.

Тут, хоть и есть квадратные корни, они в итоге дают целые числа.

Answer 4

[BaseException]

Идея следующая :
1) Считываем массив
2) Сортируем
3) Используем бинарный поиск

Comments

[dmshar]

Бинарный поиск чего? Вам же пропущенные числа неизвестны.

Answer 5

[dmshar]

Для поиска пропущенных чисел вовсе не обязательно делать последний цикл да еще и в цикле.
Достаточно один раз линейно пройти отсортированный массив от начала и да конца проверяя на каждом шаге выполняется или нет условие arr[i]==arr[i]+1, и если не выполняется - то arr[i] = это ваше число.

Можно и по другому. Если вам известна numpy, то сначала создаете нулевой массив на n позиций, потом каждое число х записываете так, что-бы arr[x]=х. А потом за один проход массива ищите те позиции, которые остались нулевыми.

Можно и еще придумать алгоритмы, которые будут работать точно быстрее, чем брутальный цикл в цикле.

Comments

[Stalker_RED]

ага, только чтобы линейно пройти придется предварительно отсортировать.

[dmshar]

Stalker_RED, aRegius, Да, только в искомом алгоритме сортировка тоже имеется, как начальный этап, ПОСЛЕ которого вложенный цикл. Да и метод поиска разности двух наборов основан на сортировке. Так что без этого никуда. Впрочем, если вы приведете алгоритм полностью без сортировки, но с более коротким временем исполнения - будет интересно посмотреть.

[aRegius]

dmshar, ?

[dmshar]

aRegius, Сорри, случайно добавилось.

Answer 6

[KabukiWarrior]

Сталкивался с. этой задачкой на Яндекс.Практикуме.

Долго мусолил решение, по-началу тоже падал на 7-м тесте. В итоге пришел к такому решению, все тесты проходят (это джава):

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int usersAmount = scan.nextInt();
        byte[] ids = new byte[usersAmount];
        int num;
        while (usersAmount > 2) {
            num = scan.nextInt();
            ids[num - 1] = 1;
            usersAmount -= 1;
        }
        int count = 0;
        for (int i = 0; i < ids.length; i++) {
            if (count<2) {
                if (ids[i] == 0) {
                    count++;
                    System.out.print((i+1) + " ");
                }
            } else {
                break;
            }
        }
    }
}