#python_3x #сортировка #list #память #время
Даны k отсортированных в порядке неубывания массивов натуральных чисел, каждое из
которых не превосходит 100. Требуется построить результат их слияния: отсортированный
в порядке неубывания массив, содержащий все элементы исходных k массивов.
Длина каждого массива не превосходит 10 ⋅ k.
Постарайтесь, чтобы решение работало за время k ⋅ log(k) ⋅ n, если считать, что входные
массивы имеют длину n.
Формат ввода
Первая строка входного файла содержит единственное число k, k ≤ 1024.
Каждая из следующих k строк описывает по одному массиву. Первое число каждой строки
равняется длине соответствующего массива, оставшиеся числа этой строки описывают значения
элементов этого же массива. Элементы массивов являются натуральными числами и не превосходят 100.
Формат вывода
Выходной файл должен содержать отсортированный в порядке неубывания массив, содержащий
все элементы исходных массивов.
Пример
Ввод
4
6 2 26 64 88 96 96
4 8 20 65 86
7 1 4 16 42 58 61 69
1 84
Вывод
1 2 4 8 16 20 26 42 58 61 64 65 69 84 86 88 96 96
Ограничение по времени выполнение скрипта 1 сек. для любого теста, ограничение по
используемой памяти: 10 МБ
Вот мой код:
import sys
int_str = ''
n = int(sys.stdin.readline().strip())
for i in range(int(n)):
s = sys.stdin.readline().strip() + ' '
count = int(s[:s.find(' ')])
p, j = 0, 0
for j in range(s.__len__()):
if s[j] == ' ':
p += 1
if p == count+1:
break
int_str += s[s.find(' '):j]
del (s,)
for i in sorted(int_str.lstrip().split(' '), key=lambda x: int(x) if x.isdigit() else 0):
print(i, end=" ")
Ещё один вариант
import sys
n = int(sys.stdin.readline().strip())
int_list = []
for i in range(n):
input = sys.stdin.readline().strip()
data = list(map(int, input.split()))
input = None
n = data[0]
a = data[1:n+1]
int_list.extend(a)
data = None
int_list.sort()
for li in int_list:
sys.stdout.write(str(li) + ' ')
sys.stdout.write('\n')
Гномья сортировка
import sys
int_list = []
t = [0] * 101
n = int(sys.stdin.readline().strip())
for i in range(int(n)):
s = sys.stdin.readline().strip()
try:
num = int(s[:s.find(' ')])
except ValueError:
continue
for index, value in enumerate(s.split(' ')):
if index == 0:
continue
elif index == num + 1:
break
try:
t[int(value)] += 1
except ValueError:
pass
del s
res = []
for i in range(101):
res += [i] * t[i]
for r in res:
print(r, end=' ')
Memory Limit и Time Limit близко
Ответы
Ответ 1
Так как в задаче есть ограничение на элементы массива:
массивов натуральных чисел, каждое из которых не превосходит 100.
то можно применить сортировку подсчётом, которая работает за линейное время.
Но для C# возникает ещё одна проблема - это создание массива строк при считывании
данных, которые на больших данных используют > 10Мб памяти. Я решила эту проблему с
помощью запуска сборщика мусора.
Моё решение:
using System;
using System.IO;
namespace ConsoleApp
{
class Program
{
static void Main(string[] args)
{
short[] digitsCount = new short[101];
short k = Convert.ToInt16(Console.ReadLine());
string[] values;
for (short i = 0; i < k; i++)
{
values = Console.ReadLine().Split(' ');
for (short j = 1; j < values.Length; j++)
{
digitsCount[Convert.ToByte(values[j])]++;
}
GC.Collect();
}
using (StreamWriter sw = new StreamWriter("output.txt"))
{
for (short i = 0; i < digitsCount.Length; i++)
{
for (short j = 0; j < digitsCount[i]; j++)
{
sw.Write(i + " ");
}
}
}
}
}
}
Удачи на собеседовании!
Ответ 2
Сложность k * n
Time Limit помогло убрать периодический вывод буфера, а не накопление его до N
k = int(input())
count = {str(i): 0 for i in range(100)}
total = 0
for list_index in range(k):
a = input().split()
size = int(a[0])
total += size
if size > 0:
for i in range(1, size + 1):
count[a[i]] += 1
buff = []
for i in range(100):
c = str(i)
if i % 10 and buff:
print(' '.join(buff), end=' ')
buff = []
buff.extend([c] * count[c])
print(' '.join(buff))
Тест list + int() vs dict vs Counter
from timeit import timeit
from collections import Counter
n = 10000000
str_list = [str(x) for x in range(n)]
number = 10
print(timeit("""
for i in range(n):
a[int(str_list[i]) % 100] += 1
""", setup='a = [0] * 100', number=number, globals=globals()))
print(timeit("""
for i in range(n):
d[str_list[i % 100]] += 1
""", setup='d = {str(i): 0 for i in range(100)}', number=number, globals=globals()))
print(timeit("""
for i in range(n):
d[str_list[i % 100]] += 1
""", setup='d = Counter(i for i in range(100))', number=number, globals=globals()))
PyPy 3.5.3 (не понятно, почему Яндекс его не добавили):
6.919497203998617
1.7934346760011977
5.253608144004829
Python 3.7
27.728900675007026
17.81548438500613
25.83648096800607
Ответ 3
Тоже столкнулся с этой задачей. Начал с Python 3.6. Пробовал сортировку подсчетом
и heapq.merge. Ни в какую не укладываюсь в 1 секунду на 20м тесте. Попробовал переписать
на Go и сортировку подсчетом. Результат по времени абсолютно такой же как на Python.
Видимо от языка не зависит.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
const k = 100
reader := bufio.NewReader(os.Stdin)
arraysNumString, _ := reader.ReadString('\n')
arraysNumString = strings.TrimSuffix(arraysNumString, "\n")
arraysNum, err := strconv.Atoi(arraysNumString)
if err != nil {
panic(err)
}
var counter [k]int
for i := 0; i < arraysNum; i++ {
inputString, _ := reader.ReadString('\n')
inputString = strings.TrimSuffix(inputString, "\n")
inputArray := strings.Split(inputString, " ")
for idx, i := range inputArray {
if idx == 0 {
continue
}
j, err := strconv.Atoi(i)
if err != nil {
panic(err)
}
counter[j]++
}
}
for index, value:= range counter {
for i := 0; i < value; i++ {
fmt.Println(index)
}
}
}
Видимо нужно искать другой алгоритм или экономить на чтении строк.
Ответ 4
В задаче не оговорен запрет на использование стандартной библиотеки, поэтому моё
решение выглядит следующим образом (для Python 3.4.3):
from collections import Counter
k = int(input())
a = Counter()
for _ in range(k):
a += Counter(map(int, input().split()[1:]))
for key, c in sorted(a.items()):
print("{} ".format(key) * c, end="")
Ключевой момент здесь в том, что элементы в вводимых массивах не могут быть больше
100, а это значит, что количество ключей для Counter() не превысит это число. Даже
в худшем случае, сортировка сотни целочисленных значений - простая задача.
Опасения у меня вызывал только момент с суммированием Counter(), однако даже в последнем
тесте, данный вариант затратил <5 mb памяти и уложился во время <0.7секунды.
Ответ 5
Реализация решения H. Case на основе встроенных типов.
Результаты - 0.522s, 4.36Mb.
n = int(input())
def counter_add(counter, value):
if value in counter:
counter[value] += 1
else:
counter[value] = 1
counter = dict()
for _ in range(n):
ar = input().split()
for i in ar[1:]:
counter_add(counter, i)
for i in range(101):
i = str(i)
if i in counter:
print(' '.join([i] * counter[i]), end=' ')
Ответ 6
Я решила вот так - по-простому:
k=int(input())
result={x:0 for x in range(0,101)}
for i in range(k):
current=input().split()[1:]
for j in range(len(current)):
cj = int(current[j])
result[cj] += 1
for key, v in result.items():
print("{} ".format(key) * v, end="")
Ответ 7
А я решил пойти путем использования одномерных векторов. Жаль, что Я не принял импорт
NumPy... Пришлось тоже через сортировку подсчетом делать. Надеюсь, будет полезно и
на такой вариант взглянуть.
import sys
import numpy as np
k = sys.stdin.readline().strip()
A = np.array([], dtype=np.uint8)
for _ in range(int(k)):
line = np.array(sys.stdin.readline().strip().split(" ")[1:], dtype=np.uint8)
A = np.append(A, line)
del line
A = np.sort(A, kind="mergesort")
A = A.tolist()
print(*A)
