Divide list into consecutive groups
https://www.careercup.com/question?id=65732
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
/**
* Created by liangzhang on 9/23/17.
*/
class Element implements Comparable<Element> {
int value;
int position;
public Element(int _value, int _position) {
value = _value;
position = _position;
}
public int compareTo(Element e2) {
return value - e2.value;
}
}
class ElementComparator implements Comparator<Element> {
public int compare(Element e, Element e2) {
return e.position - e2.position;
}
}
class ConsecutiveGroups {
// O(n) solution probably exists, but is troublesome
// instead, we will simply sort the numbers (along with their indices)
// identify the consecutive groups from the sorted list, and sort each
// group again by their indices
static ArrayList<ArrayList<Element>> group(int[] arr) {
int len = arr.length;
Element[] elements = new Element[len];
for(int i=0; i<len; i++) {
elements[i] = new Element(arr[i], i);
}
Arrays.sort(elements);
ArrayList<ArrayList<Element>> groups = new ArrayList<ArrayList<Element>>();
ArrayList<Element> group = new ArrayList<Element>();
for(int i=0; i<len; i++) {
Element element = elements[i];
if(i>0 && element.value != elements[i-1].value + 1) {
groups.add(group);
group = new ArrayList<Element>();
}
group.add(element);
}
groups.add(group);
for(ArrayList<Element> aGroup : groups) {
Collections.sort(aGroup, new ElementComparator());
}
return groups;
}
public static void main(String[] args) {
ArrayList<ArrayList<Element>> groups = group(new int[]{8,2,4,7,1,0,3,6});
for(ArrayList<Element> group : groups) {
for(Element element : group)
System.out.print(" " + element.value);
System.out.println();
}
}
}