clallenlin
BAN USERThe code stands on two premises:
1) There is only one starting point, i.e. it's not a forest
2) The route is not circulated
private ArrayList<String> getRoute(Ticket[] tickets) {
HashMap<String, String> map = new HashMap<String, String>();
for (Ticket ticket : tickets) {
if (!map.containsKey(ticket.departure)) {
map.put(ticket.departure, ticket.destination);
}
}
String start = "Circulated journey, can't find the starting point";
for (String key : map.keySet()) {
if (!map.containsValue(key)) start = key;
}
ArrayList<String> route = new ArrayList<String>();
route.add(start);
while (map.containsKey(start)) {
route.add(map.get(start));
start = map.get(start);
}
return route;
}
private class Ticket {
String departure;
String destination;
Ticket(String departure, String destination) {
this.departure = departure;
this.destination = destination;
}
}
Hi, please correct me if I'm wrong.
In my understand, your code executes partitionThreshold() twice. First in the range (0, n), second in the range (0, minimumIndex). In this case, shouldn't we only get the number of pairs with minimum (in the first partition) and the second-smallest element (in the second partition)?
If I am correct about that, we need to do a partition for every element until pivot index is 0. In this case, the average complexity is still O(n ^ 2), and the best case is O(n).
Below is my code, which is based on houseUrMusic's work:
- clallenlin May 24, 2014