CODEWITHSUNDEEP
javaarrays
daveb
daveb

Reputation: 3535

How do you split an Array List into sublists everytime there is a duplicate value in the Array List

I have the following array list which contains the following point ids (1,2,3,4,1,8,5,6,8,9,7,9). I am using Java 7

I was wondering how it could be split into sublists i.e the sublists below

(1,2,3,4,1) (8,5,6,8) (9,7,9)

I have had problems trying to use a loop within a loop (i.e check each point from the outer loop with each of the other points in the inner loop) to get
index positions (starPosIndex and endPosIndex) where there are duplicate point ids and ArrayList.sublist(startPosIndex,endPosIndex) to get the correct sublist 

int startPos = 0;
int endPos = 0;
for (int j = 0; j < polygonList3.size(); j++){
     Point pointToCheck = polygonList3.get(j);

     for (int k = 1; k < polygonList3.size(); k++){
         Point pointToCheck2 = polygonList3.get(k);
         if (pointToCheck.getID() == pointToCheck2.getID()){
             startPos = startPos + endPos;
            endPos = endPos + k;
             //startPos = startPos + endPos;
             //for (int startPos = j; startPos < polygonList3.size(); startPos = (startPos) + endPos) {
                 //endPos = Math.min(startPos + endPos, polygonList3.size());
                 finalPolygonLists.add(new ArrayList<Point>(polygonList3.subList(startPos, endPos)));//originalPtsSublist2);
             //}
         }
     }

Upvotes: 1

Views: 778

Answers (3)

Gerald M&#252;cke
Gerald M&#252;cke

Reputation: 11122

The following code tracks the last position for each number and as soon as it founds a duplicate, it will create the sublist and clears all previously tracked entries.

List<Integer> list = Arrays.asList( 1,2,3,4,1,8,5,6,8,9,7,9);

List<List<Integer>> sublists = new ArrayList<>();
Map<Integer,Integer> lastPos = new HashMap<>();

for(int i = 0; i < list.size(); i++) {
    Integer current = list.get(i);
    if(lastPos.containsKey(current)){
        sublists.add(list.subList(lastPos.get(current), i+1));
        lastPos.clear();
    } else {
        lastPos.put(current, i);
    }
}
System.out.println(sublists);

Upvotes: 0

Marco13
Marco13

Reputation: 54621

You can walk along the list, and create slices of the list (using List#subList) as you go. This can be done efficiently, by always checking whether the first element of the current segment of the list appears somewhere else in the list. If it does, you can store this "slice", and continue with the "tail" of the list. If it doesn't, you are finished (and the tail of the list may or may not be part of the result - that's up to you)

Implemented here as an example:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ListSlicing
{
    public static void main(String[] args)
    {
        runTest(1,2,3,4,1,8,5,6,8,9,7,9);
        runTest(1,2,3,4);
        runTest(1,1,1,1);
        runTest(1,2,1,2,1,2,1,2,1,2,1,2);
        runTest();
    }

    private static void runTest(Integer ... numbers)
    {
        List<Integer> list = Arrays.asList(numbers);
        System.out.println("Input:  "+list);
        System.out.println("Output: "+slices(list));
    }

    private static <T> List<List<T>> slices(List<T> input)
    {
        List<List<T>> slices = new ArrayList<List<T>>();
        List<T> current = input;
        while (current.size() > 0)
        {
            T first = current.get(0);
            int appearance = current.subList(1, current.size()).indexOf(first);
            if (appearance == -1)
            {
                slices.add(current);
                return slices;
            }
            List<T> slice = current.subList(0, appearance+2);
            slices.add(slice);
            current = current.subList(appearance+2, current.size());
        }
        return slices;
    }
}

The output is

Input:  [1, 2, 3, 4, 1, 8, 5, 6, 8, 9, 7, 9]
Output: [[1, 2, 3, 4, 1], [8, 5, 6, 8], [9, 7, 9]]
Input:  [1, 2, 3, 4]
Output: [[1, 2, 3, 4]]
Input:  [1, 1, 1, 1]
Output: [[1, 1], [1, 1]]
Input:  [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
Output: [[1, 2, 1], [2, 1, 2], [1, 2, 1], [2, 1, 2]]
Input:  []
Output: []

Upvotes: 1

James Wierzba
James Wierzba

Reputation: 17498

I would solve it in the following manner:

  1. Allocate a HashSet to contain unique values encountered
  2. Allocate a new list for the first sublist
  3. Iterate over the whole list, adding each value to the set. When we encounter a value that is already in the set, we are done with the first sublist, so clear the set, and allocate a new sublist
  4. After iteration, you will have your list of sublists, obtained in O(n) runtime

Upvotes: 2

Related Questions