i want to remove the duplicate sub integer arraylist from an integer arraylist in java

Viewed 91

you are given an nested array list such as : list = [[-1,2,1],[-2,-2,4],[-1,2,-1],[-1,-2,3],[-1,2,-1]]

i want to have an output like this : [[-1,2,1],[-2,-2,4],[-1,-2,3]]

but its not likely to come with the code i am using...

for(int i=0;i<list.size();i++){
for(int j=i+1;j<list.size();j++){
if(list.get(i).eqauls(list.get(j)))
 {
 list.remove(list.get(j));
  }
  }
  }
 System.out.println(list);

i have done like this but its not taking and duplicates are still there so i have done in another way something like this...

List<List<Integer>> list2=  new ArrayList<List<Integer>>();
for(int i=0;i<list.size();i++){
for(int j=i+1;j<list.size();j++){
if(!list.get(i).eqauls(list.get(j)))
 {
 List<Integer> p= new ArrayList<Integer>();
 for(int m=0;m<list.size();m++){
 for(int n=0;n<list.get(i).size();n++){
 p.add(list.get(i).get(m));
 list2.add(p);
 }
 }
 }
System.out.println(list2);

Output: Run time error What should i do in this case....only using array list data structures only...

4 Answers

Strategy

We can build a tree data structure, the paths of which are exactly the unique sub-lists contained within your master list. Once the tree is built, we can iterate over it, e.g. with a recursive algorithm, and re-build a master list of lists, without any duplicates.

Code

import java.util.*;

public class ListUnduper{

     public static void main(String []args){
        Tree root = new Tree();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> first = new ArrayList<Integer>(); 
        first.add(1); first.add(2);
        List<Integer> second = new ArrayList<Integer>(); 
        //Add more lists here if you like
        list.add(first); list.add(second);
        for(int i=0;i<list.size();i++){
          List<Integer> inner = list.get(i);
          Tree current = root;
          for(int j=i+1;j<inner.size();j++){
            int nextElement = inner.get(j);        
            if(!current.children.containsKey(nextElement)){
              current.children.put(nextElement, new Tree());
            }
            current = current.children.get(nextElement);
           }
        }

        List<List<Integer>> master = new ArrayList<List<Integer>>();
        List<Integer> emptyPrefix = new ArrayList<Integer>();
        addAllToList(emptyPrefix, master, root);    

        //master now should contain all non-dupes 
     }

    static void addAllToList(List<Integer> prefix, List<List<Integer>> master, Tree tree){
      for(Map.Entry<Integer,Tree> entry : tree.children.entrySet()){
        Tree nextTree = entry.getValue();  
        //I believe this makes a deep copy
        List<Integer> nextPrefix = new ArrayList<>(prefix);
        nextPrefix.add(entry.getKey());
        if(nextTree.children.isEmpty()){
          master.add(nextPrefix);
        }
        else{
          addAllToList(nextPrefix, master, tree);
        }
      }
    }
}

class Tree{
  HashMap<Integer, Tree> children = new HashMap<Integer, Tree>();
}

Warning: using recursion may result in Stackoverflow errors if your lists are large. In that case, it's advisable to switch to using a while loop, but the algorithm will likely be more complicated to code in that case.

Note on Order of Elements

As this alternative answer points out, the original order of lists within the master list may be important. The above solution does not guarantee preserving such an order.

I'm guessing this is probably a school assignment designed to get you to practice using lists and iterators and the equals() method, maybe even Comparator or Comparable. And I'm quite sure that you have not yet learned about the stream API but since your code uses List, that means you have learned about the collections framework so I don't need to explain to you what a Set is. In any case, your task can be accomplished quite easily using the stream API and the collections framework as shown in the below code. (Note that the below code uses methods introduced in Java 9.)

/* Required imports
 * 
 * import java.util.List;
 * import java.util.Set;
 * import java.util.stream.Collectors;
 */
List<List<Integer>> list2 = List.of(List.of(-1,2,1),
                                    List.of(-2,-2,4),
                                    List.of(-1,2,-1),
                                    List.of(-1,-2,3),
                                    List.of(-1,2,-1));
Set<List<Integer>> noDups = list2.stream()
                                 .collect(Collectors.toSet());
System.out.println(noDups);

Running the above code produces the following output.
(Note that iterating a Set does not guarantee any special ordering.)

[[-2, -2, 4], [-1, -2, 3], [-1, 2, -1], [-1, 2, 1]]

Refer to method equals() of interface java.util.List

EDIT

Due to Colm Bhandal's comment, and taking inspiration from artmmslv's answer, if the order is important, then the below code, which is slightly modified from the above code, will maintain the order.

List<List<Integer>> list2 = List.of(List.of(-1,2,1),
                                    List.of(-2,-2,4),
                                    List.of(-1,2,-1),
                                    List.of(-1,-2,3),
                                    List.of(-1,2,-1));
Set<List<Integer>> noDups = list2.stream()
                                 .collect(LinkedHashSet::new,
                                          LinkedHashSet::add,
                                          LinkedHashSet::addAll);
System.out.println(noDups);

The output from this code is:

[[-1, 2, 1], [-2, -2, 4], [-1, 2, -1], [-1, -2, 3]]

Put your sub-arrays to LinkedHashSet

This collection stores objects in order of addition (and does not store equal objects)

You need to code by yourself, no magic function to do for you.

You can see the sample code below.

const input = [[-1,2,1],[-2,-2,4],[-1,2,-1],[-1,-2,3],[-1,2,-1]]

const removeDuplicate = list => {
  const set = new Set()
  for (const item of list) {
     set.add(item.join('|'))
  }
  const result = Array.from(set).map(strItem => {
    const resultItem = strItem.split('|').map(item => parseInt(item))
    return resultItem
  })
  return result
}

const result = removeDuplicate(input)

console.log(result)

Related