[PAT-A] 1097 Deduplication on a Linked List

Java

测试点3、4超时

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static final int N = 100010;
    static int h, n;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static boolean[] st = new boolean[N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        h = Integer.parseInt(input[0]);
        n = Integer.parseInt(input[1]);

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            int addr = Integer.parseInt(line[0]);
            int key = Integer.parseInt(line[1]);
            int next = Integer.parseInt(line[2]);
            e[addr] = key;
            ne[addr] = next;
        }

        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();

        for (int i = h; i != -1; i = ne[i]) {
            int v = Math.abs(e[i]);
            if (st[v]) {
                b.add(i);
            } else {
                st[v] = true;
                a.add(i);
            }
        }

        for (int i = 0; i < a.size(); i++) {
            System.out.printf("%05d %d ", a.get(i), e[a.get(i)]);
            if (i + 1 == a.size()) {
                System.out.println("-1");
            } else {
                System.out.printf("%05d\n", a.get(i + 1));
            }
        }
        for (int i = 0; i < b.size(); i++) {
            System.out.printf("%05d %d ", b.get(i), e[b.get(i)]);
            if (i + 1 == b.size()) {
                System.out.println("-1");
            } else {
                System.out.printf("%05d\n", b.get(i + 1));
            }
        }
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 100010;

int n;
int h, e[N], ne[N];
bool st[N];

int main() {
    scanf("%d%d", &h, &n);
    for (int i = 0; i < n; i++) {
        int addr, key, next;
        scanf("%d%d%d", &addr, &key, &next);
        e[addr] = key, ne[addr] = next;
    }

    vector<int> a, b;
    for (int i = h; i != -1; i = ne[i]) {
        int v = abs(e[i]);
        if (st[v]) b.push_back(i);
        else {
            st[v] = true;
            a.push_back(i);
        }
    }

    for (int i = 0; i < a.size(); i++) {
        printf("%05d %d ", a[i], e[a[i]]);
        if (i + 1 == a.size()) puts("-1");
        else printf("%05d\n", a[i + 1]);
    }
    for (int i = 0; i < b.size(); i++) {
        printf("%05d %d ", b[i], e[b[i]]);
        if (i + 1 == b.size()) puts("-1");
        else printf("%05d\n", b[i + 1]);
    }

    return 0;
}