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();
        }
    }
}

results matching ""

    No results matching ""