4 / 3 / 1
Регистрация: 25.10.2019
Сообщений: 10
1

Для каждого числа из второго списка вывести индекс первого и последнего вхождения в первый список

07.11.2019, 22:40. Показов 2918. Ответов 8
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть задача:

Вам даны два списка целых чисел.
Первый список отсортирован по возрастанию.
Необходимо для каждого числа из второго списка вывести индекс первого и последнего вхождения в первый список.
Если числа нет, то выведите два числа -1 и -1.

В задаче есть ограничения:

Ограничение времени 1.4 секунды
Ограничение памяти 256Mb

Решил таким образом:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import bisect
s = str(input())
s_1 = s.split(' ')
s_2 = [int(item) for item in s_1]
 
r = str(input())
r_1 = r.split(' ')
r_2 = [int(item) for item in r_1]
 
i=0
for i in range (len(r_2)):
  if r_2[i] in s_2:
    print ((bisect.bisect_left(s_2, r_2[i])), (bisect.bisect_right(s_2, r_2[i])-1))
  else:
    print ('-1 -1')
  i = i+1
Но не укладываюсь по времени, у меня 1.684s / 4.88Mb

Подскажите как можно оптимизировать код.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.11.2019, 22:40
Ответы с готовыми решениями:

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

Вывести на индекс первого и последнего минимального значения для каждого ряда
Для матрицы со стороной 10, заполненной числами от 0 до 9 вывести на экран индексы первого и...

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

Если первый и последний элементы списка-аргумента - символы, то сформировать список с первого и последнего элементов, иначе вернуть начальный список
Напишите, пожалуйста, функцию, которая для аргумента-списка формирует список-результат за правилом:...

8
3486 / 2094 / 560
Регистрация: 02.09.2015
Сообщений: 5,339
07.11.2019, 22:53 2
Olmaris, не смущает эта строка?
Цитата Сообщение от Olmaris Посмотреть сообщение
if r_2[i] in s_2:
1
4 / 3 / 1
Регистрация: 25.10.2019
Сообщений: 10
07.11.2019, 23:05  [ТС] 3
Смущает, очень, но как проверить, что число входит в строку, или же печать -1 -1
0
3486 / 2094 / 560
Регистрация: 02.09.2015
Сообщений: 5,339
07.11.2019, 23:11 4
Olmaris, проверяете:
Python
1
2
3
4
5
bl_index = bisect_left(s_2, r_2[i]))
if bl_index < len(s_2) and s_2[bl_index] == r_2[i]:
    # что-то там
else:
    # -1 -1
1
4 / 3 / 1
Регистрация: 25.10.2019
Сообщений: 10
08.11.2019, 13:05  [ТС] 5
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import bisect
s = str(input())
s_1 = s.split()
s_2 = [int(item) for item in s_1]
 
r = str(input())
r_1 = r.split()
r_2 = [int(item) for item in r_1]
 
i=0
for i in range (len(r_2)):
  bl_index = bisect.bisect_left(s_2, r_2[i])
  if bl_index < len(s_2) and s_2[bl_index] == r_2[i]:
    print (bl_index, (bisect.bisect_right(s_2, r_2[i])-1))
  else:
    print ('-1 -1')
  i = i+1
Существенно не изменилось: 1.639s против 1.684s ранее.
0
3486 / 2094 / 560
Регистрация: 02.09.2015
Сообщений: 5,339
08.11.2019, 16:32 6
Olmaris, http://labs.tspu.edu.ru/doku.p... 7%D0%B0_21
1
4 / 3 / 1
Регистрация: 25.10.2019
Сообщений: 10
08.11.2019, 17:08  [ТС] 7
Цитата Сообщение от Arsegg Посмотреть сообщение
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def UpperBound(A, key):
  left = -1
  right = len(A)
  while right - left > 1:
    middle = (left + right) // 2
    if A[middle] <= key:
      left = middle
    else:
      right = middle
  return right
 
def LowerBound(A, key):
  left = -1
  right = len(A)
  while right - left > 1:
    middle = (left + right) // 2
    if A[middle] < key:
      left = middle
    else:
      right = middle
  return right
 
A = list(map(int, input().split()))
for key in input().split():
  key = int(key)
  lower = LowerBound(A, key)
 
  upper = UpperBound(A, key)
  if lower < len(A) and A[lower] == key:
    print(lower, upper - 1)
  else:
    print ('-1 -1')
Тут с таймингами еще хуже: 1.694s - у них в задании дают две секунды, а у нас полторы
0
3486 / 2094 / 560
Регистрация: 02.09.2015
Сообщений: 5,339
08.11.2019, 20:42 8
Olmaris, тогда пишите на C/C++. Быстрее не получится.
0
4 / 3 / 1
Регистрация: 25.10.2019
Сообщений: 10
08.11.2019, 21:41  [ТС] 9
Оптимизировал на операциях ввода данных:

Python
1
2
3
4
5
6
7
8
9
10
11
import bisect
s_2 = list(map(int, input().split()))
r_2 = list(map(int, input().split()))
i=0
for i in range (len(r_2)):
  bl_index = bisect.bisect_left(s_2, r_2[i])
  if bl_index < len(s_2) and s_2[bl_index] == r_2[i]:
    print (bl_index, (bisect.bisect_right(s_2, r_2[i])-1))
  else:
    print ('-1 -1')
  i = i+1
Итог: 1.255s

Arsegg, большое спасибо за ответы, все оказалось не так страшно, как казалось с первого взгляда.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.11.2019, 21:41
Помогаю со студенческими работами здесь

Вывести для каждого из символов позицию последнего вхождения в заданную последовательность
Ввести с клавиатуры массив char -&gt; S &amp;&amp; string STR . Выделить в ней все существующие символы и...

Удалить из второго списка все вхождения головы первого списка
2. Даны 2 списка. Удалить из второго все вхождения головы первого списка.

Вывести для каждого из символов позицию его последнего вхождения в заданную последовательность
Есть такое задание.Дана последовательность символов С. Выделить в ней все имеющиеся символы и...

Вывести на индекс первого и последнего минимального значения для каждой строки
Для матрицы со стороной 10, заполненной числами от 0 до 9 вывести на экран индексы первого и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru