Как осуществить слияние k сортированных списков

#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)