juando.martin
BAN USERWell that is not exactly my idea. Than does not run in O(n) as you update nodes in the table that need not. Take into account that once a node is stored it will never be checked again unless a neighbor is checked in too for the first time, so you only need to keep updated the extremes of a chain.
The code would be for the node class just the same:
import java.util.HashMap;
class Node {
Integer first;
Integer last;
Node(Integer first_int, Integer last_int) {
this.first = first_int;
this.last = last_int;
}
}
But for the Consecutive string class:
import java.util.HashMap;
public class ConsecutiveString {
public static void main(String[] args) {
Integer max_length = 0;
Node max_chain = null;
HashMap<Integer, Node> table = new HashMap<Integer, Node>();
Integer[] numbers = { 101, 2, 3, 104, 5, 103, 9, 102 };
for (Integer number : numbers) {
if (table.containsKey(number)) {
continue;
} else {
Node here;
if (table.containsKey(number - 1)) {
Node left = table.get(number - 1);
if (table.containsKey(number + 1)) {
Node right = table.get(number + 1);
// We have both left and right. Link them and
// store in both sides
left.last = right.last;
right.first = left.first;
here = left; // Or right, it's the same
} else {
// there is a node at our left, but not at the right.
left.last = number;
table.put(number, left);
here = left;
}
} else if (table.containsKey(number + 1)) {
// We have only a node at our right
Node right = table.get(number + 1);
right.first = number;
here = right;
} else {
// No other node around
here = new Node(number, number);
}
table.put(number, here);
int length = here.last - here.first + 1;
if (length > max_length) {
max_length = length;
max_chain = here;
}
}
}
System.out.println(max_chain.first.toString() + " - " +
max_chain.last.toString());
}
}
The problem with this approach is that as chains grow you have to repeatedly go over each element in the chain updating, so it is no longer O(n)
- juando.martin July 18, 2011One run with one hash table:
Keep in hash table using the numbers as keys of a structure containing two numbers: the first (F) and the last (L) element of a possible chain. Only first and last element of the chain need to be properly updated. When you insert an element N in the table check also for the neighbors (N-1 and N+1). We will call '(N)->F' The number stored as first of a possible chain in the Nth position and '(N)->L' the number stored as last of the chain. Possible cases are:
- The number is already there => Do nothing.
- No neighbors => make a single-node chain storing the number as first and last in its own position:
(N)->F = N
(N)->L = N
- Only the left neighbor is present => The number becomes the last element in the chain. Get the first element of the chain from the left neighbor and update the chain info:
(N)->L = N
(N)->F = (N-1)->F
((N-1)->F)->L = N
- Only right neighbor is present => Similar to previous
(N)->F = N
(N)->L = (N+1)->L
((N+1)->L)->F = N
- Both neighbors are present => Link two chains updating the first of the left and last element of the right:
((N-1)-F)->L = (N+1)->L
((N+1)->L)->F = (N-1)-F
Each time you update a chain you can easily compute the length. Keep track of the largest one storing in a couple variables its length and its first element and updating as required.
Well, it was not the idea that is wrong, but the code. I did not realize that cannot get the ends of the chain through the nodes, but rather through the table. As I said you don't have to modify all the nodes, only the ends. Here is the (hopefully) right code. Only a couple of indirections added to my previous.
- juando.martin February 10, 2013