smashs
BAN USERIn short
M =
0 0 0 X
0 0 X N
0 X N N
X N N N
is a sorted matrix, where N is a very large number (choose infinity if you like) the element we are looking for(say '5') can be in any of the 'X' s. any algorithm has to search at-least those 'X' elements on the diagonal, because there are no ordering imposed on those elements by the definition of the matrix. simply put there can be no algorithm that takes less than linear time
- smashs March 31, 2012O(n) time complexity
Simultaneously go through the list by ones (slow iterator) and by twos (fast iterator). If there is a loop the fast iterator will go around that loop twice as fast as the slow iterator. The fast iterator will lap the slow iterator within a single pass through the cycle. Detecting a loop is then just detecting that the slow iterator has been lapped by the fast iterator.
// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode = startNode;
while (slowNode && fastNode)
{
if (slowNode == fastNode) return true;
slowNode = slowNode.next();
fastNode = fastNode.next();
if (slowNode == fastNode) return true;
fastNode = fastNode == null? null : fastNode.next();
}
return false;
}
This solution is "Floyd's Cycle-Finding Algorithm" as published in "Non-deterministic Algorithms" by Robert W. Floyd in 1967. It is also called "The Tortoise and the Hare Algorithm".
- smashs March 31, 2012
Repryandchinkle, Android Engineer at ABC TECH SUPPORT
I was born in Northridge USA, I like photography, I have wide photos collection of wildlife. I have many religious ...
Repmarybritt, Android Engineer at Centro
I am Mary from Wilmington. I am working as a Graphic Designer in Super Enterprises. I also write articles and ...
Repcharlesgwitt47, Animator at ASU
By Profession, I am a Automotive service technician in Kennewick USA. My strong interest is in yoga, My yogic journey ...
there are no sub-linear solution, the search space is O(n2) (i.e. all pair sums of the array), and its proven that you can not do better than linear time. you can google selection in X+Y sorted arrays to see the general problem.
- smashs April 06, 2012