CODEWITHSUNDEEP
javaarraylistcollections
yasin
yasin

Reputation: 43

Java ArrayList adding values with same Id

So I have a an array List that looks like this: <id,value,id,value,...>and I should find all the elements with the same id and add together there respected values into a result array list (value always comes after the id). At first I thought the problem was easy and went ahead and tried this:

        List<String> resultList = new ArrayList<>();
        for(int i = 0; i < myList.size(); i+=2){

            BigInteger currentID = new BigInteger(myList.get(i));
            BigInteger currentSum = new BigInteger(myList.get(i+1));
            String currentId = myList.get(i);
            int j = 2;

            while(j < myList.size()){
                if(currentId.equals(myList.get(j))){
                 BigInteger value2 = new BigInteger(myList.get(j+1));
                 currentSum = currentID.add(value2);
                }
                resultList.add(currentId);
                resultList.add(String.valueOf(currentSum));
                j+=2;
            }
        }

Needless to say it isn't correct, one of the many problems is that values which haven been already added together will be readded into the result array so I think they should be removed somehow in the loop. Do you guys have any suggestions how to go around this?

Upvotes: 4

Views: 2709

Answers (3)

Stephen C
Stephen C

Reputation: 718788

It is easiest to do this using a Map. But it can also be done without changing the input data structure, or using any intermediate data structure.

Here is an untested code sample. I have simplified the problem by using List<Integer>

    List<Integer> myList = ...
    List<Integer> resultList = new ArrayList<>();

    for (int i = 0; i < myList.size(); i += 2) {
        int id = myList.get(i);

        // Check that we haven't accumulated this id already
        boolean seen = false;
        for (int j = 0; j < i && !seen; j += 2) {
            seen = myList.get(j) == id;
        }
        if (seen) {
            continue;
        }

        // Accumulate values for 'id'
        int sum = myList.get(i + 1);
        for (int j = i + 2; j < myList.size(); j += 2) {
            if (myList.get(j) == id) {
                sum += myList.get(j + 1);
            }
        }
        // Send to output ...
        resultList.add(id);
        resultList.add(sum);
    }

This solution is O(N^2). And since you are actually using String and BigInteger rather than Integer, that makes it even more expensive.

A solution using a Map should be O(NlogN) or O(N) depending on the map type.

Aside: It would be faster in some cases if you used resultList rather than myList in the first inner loop. But the way I did it above is more obvious ...

Upvotes: 1

WJS
WJS

Reputation: 40034

If you want to use streams you can do it like this.

Given a list like the following:

      List<BigInteger> list = List.of(1,10,3,20,3,40,1,5,4,7,1,8,4,9,6,20)
           .stream().mapToLong(a -> a).mapToObj(
                  BigInteger::valueOf).collect(Collectors.toList());

First accumulate the sums in a map with the key being the id.

      Map<BigInteger, BigInteger> mapfinal =
            IntStream.iterate(0, i -> i < list.size(), i -> i += 2).mapToObj(
                  i -> new BigInteger[] { list.get(i), list.get(i + 1)
                  }).collect(Collectors.groupingBy(i -> i[0],
                        Collectors.reducing(BigInteger.ZERO,
                              a -> a[1],
                              (a, b) -> a.add(b))));

You can stop there and just use the map, or you can convert it to a list like the one you started with of alternating id/value pairs.

       List<BigInteger> listfinal = mapfinal
            .entrySet()
            .stream()
            .flatMap(e -> Stream.of(e.getKey(), e.getValue()))
            .collect(Collectors.toList());

And print the list.

      System.out.println(listfinal);

[1, 23, 3, 60, 4, 16, 6, 20]

Upvotes: 2

Loading...
Loading...

Reputation: 119

Assuming you can use a Map: My initial thought it to use a Map<String, String> map = new HashMap();

Pseudo code:
For each (id,value pair) in resultList
   if map.get(id) exists
      add the value to the existing entry in the map
   else 
      add a new entry in the map for (id,value)

As code (NOTE: untested and might not compile, wouldn't copy & paste directly):

Map<String, String> map = new HashMap<>();
for(int i = 0; i < myList.size(); i+=2){
   String listId = resultList.get(i); //get the Id from the resultList
   String listValue = resultList.get(i+1) //get the value from the resultList
   if(map.get(listId) != null) { // if the map has this Id
      map.put(listId, map.get(listId)+ listValue); // add the Id's list value
   }
   else { // if the map doesn't have this Id
      map.put(listId, listValue) // add the entry to the map
   }
}

You can then take the resulting map and transform is back into a list. I'll let you write the code to take each entry in the map and add it to a new List. Google can be helpful here.

Upvotes: 4

Related Questions