Yandex Contest Удаление дубликатов java

Я тоже много времени потратил на это задание. Переделал код полностью на статические вызовы, убрал создание новых объектов. Пробовал даже периодически вызывать System.gc() :) Но оказалось, что ключевым моментом стал уход от использования System.in и System.out.

Ниже приведенное решение позволяет уложиться в ограничения по времени и памяти с запасом (251ms и 10.87Mb). Так конечно не следует в общем случае писать на Java, но производительность же..

import java.io.*;

public class Solution {
    static final int MAX_INT_LENGTH = 12;

    static final String input = "input.txt";
    static final String output = "output.txt";

    static BufferedReader r;
    static BufferedWriter w;

    static final char[] curr = new char[MAX_INT_LENGTH];
    static final char[] prev = new char[MAX_INT_LENGTH];

    public static void main(String... args) throws IOException {
        r = new BufferedReader(new FileReader(input));
        w = new BufferedWriter(new FileWriter(output));

        int n = Integer.parseInt(r.readLine());
        if (n < 1) return;

        readCurr();
        copyCurrToPrev();
        printCurr();

        for (int i = 0; i < n - 1; i++) {
            readCurr();
            if (!currEqualsPrev()) {
                printCurr();
                copyCurrToPrev();
            }
        }
        r.close();
        w.close();
    }

    private static void readCurr() throws IOException {
        int b = 0;
        for (int i = 0; i < MAX_INT_LENGTH; i++) {
            b = r.read();
            if (b < 0) {
                curr[i] = '\n';
                break;
            }
            curr[i] = (char) b;
            if (b == '\n') break;
        }
    }

    private static void printCurr() throws IOException {
        for (int i = 0;; i++) {
            w.write(curr[i]);
            if (curr[i] == '\n') break;
        }
    }

    private static boolean currEqualsPrev() {
        for (int i = 0; i < MAX_INT_LENGTH; i++) {
            if (curr[i] != prev[i]) return false;
            if (curr[i] == '\n') break;
        }
        return true;
    }

    private static void copyCurrToPrev() {
        for (int i = 0; i < MAX_INT_LENGTH; i++) {
            prev[i] = curr[i];
            if (curr[i] == '\n') break;
        }
    }
}

Вот мое решение - 162ms 8.76Mb. Все сводится к низкоуровневым операциям.

import java.io.*;
import java.util.Arrays;

public class Contest {
    public static void main(String... args) throws Exception {
        byte[] buffer = new byte[128];
        byte[] lastValue = new byte[128];
        int lastValueSize = 0;

        try (BufferedInputStream bis = new BufferedInputStream(new FileInputStream("input.txt"), 8192);
             BufferedOutputStream bos = new BufferedOutputStream(new FileOutputStream("output.txt"), 8192)) {

            int countValueSize = readValue(bis, buffer);
            int count = Integer.parseInt(new String(Arrays.copyOfRange(buffer, 0, countValueSize)));
            for (int i = 0; i < count; i++) {
                int nextValueSize = readValue(bis, buffer);

                if (i == 0 || !isValuesEqual(buffer, nextValueSize, lastValue, lastValueSize)) {
                    bos.write(buffer, 0, nextValueSize);
                    bos.write('\n');

                    System.arraycopy(buffer, 0, lastValue, 0, nextValueSize);
                    lastValueSize = nextValueSize;
                }
            }
        }
    }

    private static int readValue(InputStream is, byte[] buffer) throws IOException {
        int counter = 0;
        int i;
        while ((i = is.read()) != '\n' && i > 0) {
            buffer[counter++] = (byte)i;
        }

        return counter;
    }

    private static boolean isValuesEqual(byte[] first, int firstSize, byte[] second, int secondSize) {
        if(firstSize != secondSize) {
            return false;
        }

        for(int i = 0; i < firstSize; i++) {
            if(first[i] != second[i]) {
                return false;
            }
        }

        return true;
    }
}

Тоже долго не мог пройти все тесты, прочитал ответ здесь, поменял в своём решении, которое не проходило 193-й тест по памяти чтение из System.in на чтение и запись в файлы, при выборе компилятора Oracle Java 7 это решение принимается как корректное, при выборе компилятора Oracle Java 8 это же решение получает ошибку превышения ограничения по памяти на 193-м тесте. Что немного настораживает, аналогично было и по другому заданию - D - Генерация скобочных последовательностей.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
public class Third {
    static final String input = "input.txt";
    static final String output = "output.txt";
    static BufferedReader br;
    static BufferedWriter bw;
    
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new FileReader(input));
        bw = new BufferedWriter(new FileWriter(output));
        int n = Integer.valueOf(br.readLine());
        String last = "";
        String curr = last;
        for (int i = 0; i < n; i++) {
            curr = br.readLine().intern();
            if (last != curr) {
                last = curr;
                bw.write(curr);
                bw.write('\n');
            }
        }
        br.close();
        bw.close();
    }
}

Я сначала попробовал использовать коллекции для сортировки уникальных значений.

Множество Set хранит ведь только уникальные значения.

import java.io.*;
import java.util.HashSet;
import java.util.Set;

public class WooHoo {

    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));


        int n = Integer.parseInt(r.readLine());
        int currentCount = 0;
        Set<Integer> checkSet = new HashSet<>();
        while (currentCount < n) {
            int elem = Integer.parseInt(r.readLine());
            checkSet.add(elem);
            currentCount++;
        }
        checkSet.stream().iterator().forEachRemaining(System.out::println);
    }

}

Но завалился на 193 тесте по времени выполнения.

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

Так как в условии задачи о входных данных сказано:Числа отсортированы по неубыванию.

После чего реализовал

public class WooHoo {

    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(r.readLine());
        String lastUniqueElement = "";
        for(int i = 0; i < n; i++) {
            String elem = r.readLine();
            if (!elem.equals(lastUniqueElement)){
                lastUniqueElement = elem;
                System.out.println(lastUniqueElement);
            }
        }
    }

}

Данный код уже прошёл все проверки