dauren101
@dauren101
Python, Django ,Vue.js

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

В сервисе Киношечка зарегистрировано 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 очень много.
Как можно оптимизировать алгорит?
  • Вопрос задан
  • 957 просмотров
Решения вопроса 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))
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
Stalker_RED
@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
Ответ написан
wataru
@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.

Тут, хоть и есть квадратные корни, они в итоге дают целые числа.
Ответ написан
Комментировать
@BaseException
Идея следующая :
1) Считываем массив
2) Сортируем
3) Используем бинарный поиск
Ответ написан
@dmshar
Для поиска пропущенных чисел вовсе не обязательно делать последний цикл да еще и в цикле.
Достаточно один раз линейно пройти отсортированный массив от начала и да конца проверяя на каждом шаге выполняется или нет условие arr[i]==arr[i]+1, и если не выполняется - то arr[i] = это ваше число.

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

Можно и еще придумать алгоритмы, которые будут работать точно быстрее, чем брутальный цикл в цикле.
Ответ написан
@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;
            }
        }
    }
}
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы