Java - 特定链表序列化[关闭]

问题描述 投票:1回答:2

我有ListRand结构:

class ListRand
{
    public ListNode Head;
    public ListNode Tail;
    public int Count;

    public void Serialize(FileStream s)
    {
    }

    public void Deserialize(FileStream s)
    {
    }
}

这是由ListNodes组成的:

class ListNode
{
    public ListNode Prev;
    public ListNode Next;
    public ListNode Rand; // random element in list
    public string Data;
}

问题是:如何实现SerializeDeserializeListRand方法,其复杂度优于O(N * N)

更新,感谢@HonzaZidek和@JoopEggen,我的最终解决方案是(我没有在实际数据上测试它)

public class ListNode {
public ListNode prev;
public ListNode next;
public ListNode rand; // random element inside the list
public String data;
}


class ListRand {
public ListNode head;
public ListNode tail;
public int count;

public void serialize(FileOutputStream fileOutputStream) {

    // value is index of rand
    Map<ListNode, Integer> map = new HashMap<>();
    ListNode node = head;

    // assigning indexes for all ListNodes sequentially
    int index = 0;
    do {
        map.put(node, index);
        node = node.next;
        index++;

    } while (node != null);

    // iterate over map and write data and random index to fileOutputStream
    for (Map.Entry<ListNode, Integer> entry : map.entrySet()) {

        ListNode key = entry.getKey();
        ListNode rand = key.rand;

        String outputString = (rand == null) ?
                key.data + " " + "-1" + "\n" :
                key.data + " " + map.get(rand) + "\n";

        try {
            fileOutputStream.write(outputString.getBytes());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

public ListRand deSerialize(FileInputStream fileInputStream) {

    ListRand result = new ListRand();
    ListNode head = new ListNode();
    result.head = head;

    BufferedReader reader = new BufferedReader(new InputStreamReader(fileInputStream));
    String line;

    List<ListNode> nodes = new ArrayList<>();
    List<Integer> indexes = new ArrayList<>();
    ListNode current = head;

    try {

        // read data and create linked list structure - O(N) complexity
        while ((line = reader.readLine()) != null) {
            String[] dataArray = line.trim().split(" ");
            String data = dataArray[0];
            Integer randomIndex = Integer.parseInt(dataArray[1]);

            ListNode next = new ListNode();
            current.next = next;
            current.data = data;

            next.prev = current;

            nodes.add(current);
            current = next;

            indexes.add(randomIndex);
        }

        // assign null to last node's next element
        ListNode lastNode = nodes.get(nodes.size() - 1);
        lastNode.next = null;

        // iterate over map and write data and random index to fileOutputStream - O(N) complexity
        for (int i = 0; i < nodes.size(); i++) {

            // get by index - O(1) complexity
            ListNode node = nodes.get(i);
            Integer randIndex = indexes.get(i);
            node.rand = (randIndex == -1) ? null : nodes.get(randIndex);
        }

        result.count = nodes.size();
        result.tail = nodes.get(nodes.size() - 1);

    } catch (IOException e) {
        e.printStackTrace();
    }

    return result;
}
}
java serialization linked-list deserialization structure
2个回答
2
投票

从Head序列化所有Next。然后(拥有所有节点)从Head序列化所有Rand作为参考(例如索引号)。

  • First Head + Nexts循环O(N)
  • 然后映射Rand:O(N.log N)作为一个节点的查找是log N.
  • 完全O(N.log N)

你应该已经意识到了这一点。我留给你的实现,因为这似乎是一些CS课程的任务。


2
投票

我可以看到如何实现O(N)时间复杂度的一些可能性。在这两种情况下,您只需将列表序列化为一系列元组(数据,随机节点的索引)。

  1. 正如Serge Ballesta在评论中建议的那样,读取所有节点并创建一个哈希映射,初始容量足够大,将ListNodes映射到索引。如果哈希码设计得很好并且运气不好(不太可能),那么这将是线性的。 如果你的ListNode没有定义hashCode()equals(),你将创建一个包装类,使用ListNode作为其唯一属性,将其用作地图中的键。但是,因为你总是认为ListNode的两个实例不相等,它实际上也适用于equals()hashCode()的默认实现,因为它们的hashCode()的“正常”实现将足够好。虽然documentation没有严格要求:

尽管合理实际,但是由Object类定义的hashCode方法确实为不同的对象返回了不同的整数。 (hashCode可能会或可能不会在某个时间点实现为对象的内存地址的某些功能。)

  1. 如果允许向ListNode添加属性 - 添加索引。此属性仅在序列化之前分配并有效。在序列化之前,锁定列表,迭代它并为每个节点分配其索引。这将比哈希映射消耗更少的内存,并且将具有确定性线性。
© www.soinside.com 2019 - 2024. All rights reserved.