我有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;
}
问题是:如何实现Serialize
的Deserialize
和ListRand
方法,其复杂度优于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;
}
}
从Head序列化所有Next。然后(拥有所有节点)从Head序列化所有Rand作为参考(例如索引号)。
O(N)
O(N.log N)
作为一个节点的查找是log N.O(N.log N)
你应该已经意识到了这一点。我留给你的实现,因为这似乎是一些CS课程的任务。
我可以看到如何实现O(N)时间复杂度的一些可能性。在这两种情况下,您只需将列表序列化为一系列元组(数据,随机节点的索引)。
ListNode
s映射到索引。如果哈希码设计得很好并且运气不好(不太可能),那么这将是线性的。
如果你的ListNode
没有定义hashCode()
和equals()
,你将创建一个包装类,使用ListNode
作为其唯一属性,将其用作地图中的键。但是,因为你总是认为ListNode
的两个实例不相等,它实际上也适用于equals()
和hashCode()
的默认实现,因为它们的hashCode()
的“正常”实现将足够好。虽然documentation没有严格要求:尽管合理实际,但是由Object类定义的
hashCode
方法确实为不同的对象返回了不同的整数。 (hashCode
可能会或可能不会在某个时间点实现为对象的内存地址的某些功能。)
ListNode
添加属性 - 添加索引。此属性仅在序列化之前分配并有效。在序列化之前,锁定列表,迭代它并为每个节点分配其索引。这将比哈希映射消耗更少的内存,并且将具有确定性线性。