1

Пытаюсь решить задачку, вроде все правильно, но тесты выдают ошибку. Подскажите где я ошибся в решении?

Задача: Даны 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

Решение:

const buf = Buffer.allocUnsafe(10000) // Создаю буффер.
let pos = 0
const fs = require('fs')
const path = require('path')
const fd = path.join(__dirname, '/input.txt')
var fp = fs.openSync(fd, 'r')

fs.read(fp, buf, 0, 4, pos, function (err, bytesRead, buff) { // - считываю количество строк
  if (err) return
  const stringsAmount = buff.toString('utf8').split('\n')[0]
  const length = stringsAmount * 10
  const resultArray = []
  let count = 0
  pos += stringsAmount.length + 1
  readNextChunk(length)
  function readNextChunk (length) {
    fs.read(fp, buf, 0, length, pos,   //  начинаю бежать частями, длина части = кол-во строк * 10
      function (err) {
        if (err) throw err
        const arrstr = buf.toString('utf8').split('\n')[0]
        buf.fill(0) // clear buffer
        const arr = arrstr.split(' ')
        for (let i = 1; i < arr.length; i++) { // наполняю результирующий массив сортировкой подсчетом
          if (resultArray[arr[i]]) {
            resultArray[arr[i]]++
          } else {
            resultArray[arr[i]] = 1
          }
        }
        pos += arrstr.length + 1 //переношу позицию прибавляя длину считанного массива
        count++
        if (count < stringsAmount) {
          readNextChunk(length)
        } else {
          const res = []
          for (let i = 0; i < 101; i++) {
            if (resultArray[i]) {
              for (let j = 0; j < resultArray[i]; j++) {
                process.stdout.write(i.toString() + ' ') // вывожу результат
              }
            }
          }
        }
      })
  }
})

7
  • А зачем так все усложнять со считыванием файла через буфер, если есть readline?
    – Yaant
    8 дек 2019 в 15:15
  • А по сути вопроса, обратите внимание, что если запустить Ваш код на приведенных входных данных, то в выводе отсутствуют последние элементы каждого из входных списков.
    – Yaant
    8 дек 2019 в 15:18
  • @Yaant, из за ограничений по памяти 8 дек 2019 в 15:46
  • Это что за драконовские ограничения? Там же максимальная длина одной строки в исходном файле - 30 килобайт, у Вас памяти ещё меньше?
    – Yaant
    8 дек 2019 в 15:52
  • @Yaant, ограничение 20 мб, если считывать все строки readline, то идет превышение по тестам 8 дек 2019 в 15:55

1 ответ 1

1

Может кому-то пригодится, решение через рекурсию со счетчиком количества строк. Решение прошло все тесты.

const readline = require('readline')
const fs = require('fs')
const path = require('path')
const rl = readline.createInterface({
  input: fs.createReadStream(path.join(__dirname, 'input.txt'))
})
const array = []
rl.once('line', (line) => {
  let counter = 0
  const readline = () => {
    if (counter === +line) {
      for (let i = 0; i < 101; i++) {
        if (array[i]) {
          let str = ''
          for (let j = 0; j < array[i]; j++) {
            str += i.toString() + ' '
          }
          const fd = fs.openSync(path.join(__dirname, 'output.txt'), 'a')
          fs.writeSync(fd, str)
          fs.closeSync(fd)
        }
      }
      return
    }
    counter++
    rl.once('line', arr => {
      arr = arr.match(/\d+/g)
      for (let i = 1; i < arr.length; i++) {
        if (array[arr[i]]) {
          array[arr[i]]++
        } else {
          array[arr[i]] = 1
        }
      }
      readline()
    })
  }
  readline()
})

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.