Arraylist Comparison using one loop

Question

It has been a long since something came to my mind while starting to code and using lists or array lists. When comparing values of one array to every other elements in another array, I used to do it in two for loops since it was the easiest way to do that.but recently I came to know that it increases much time complexity, I thought about another solution.can anyone help me in solving this case using any algorithm. I am using java.but solution in any language would be fine. just the algorithm to do that is needed. Thanks in advance.

This is what i am doing:

a1 = [1,2,3,4,5]
b1 = [9,5,4,3,8,3,7]

I want to check how much time an element in a1 occurs in b1

So what i am doing is:

count = 0;

    for(int i = 0;i <a1.length;i++)
    {
      for(j=0;j<b1.length;j++)
       {
         if (a1[i] == b1[j])
          {
           count = count+1;
           }
         }
      }

    print("count is" count);

Use [hashing](https://en.wikipedia.org/wiki/Hash_function), e.g. with a `Set` or `Map`. — tobias_k, Nov 28 '19 at 13:26
Define what you mean by "comparing". Post the method you have written, and explain what it's supposed to do. Give example inputs and outputs. — JB Nizet, Nov 28 '19 at 13:26
can anyone mention any algorithm for doing this process in one array — Abraham Baby, Nov 28 '19 at 13:32

tobias_k · Answer 1 · 2019-11-28T14:59:35.917

Use hashing, e.g. using a Set or Map

If you want to compare the objects as a whole:

properly implement equals and hashcode for your class (if not implemented already)
put all the elements of list A into a Set, then see which elements from list B are in that Set

If you just want to compare objects by some attribute:

define a method that maps the objects to that attribute (or combination of attriutes, e.g. as a List)
create a Map<KeyAttributeType, List<YourClass>> and for each element from list A, add the element to that Map: map.get(getKey(x)).add(x)
for each element from list B, calculate the value of the key function and get the elements it "matches" from the map: matches = map.get(getKey(y))

Given your code, your case seems to be a bit different, though. You have lists or arrays of numbers, so no additional hashing is necessary, and you do not just want to see which items "match", but count all combinations of matching items. For this, you could create a Map<Integer, Long> to count how often each element of the first list appears, and then get the sum of those counts for the elements from the second list.

int[] a1 = {1,2,3,4,5};
int[] b1 = {9,5,4,3,8,3,7};
Map<Integer, Long> counts = IntStream.of(b1).boxed()
        .collect(Collectors.groupingBy(x -> x, Collectors.counting()));
System.out.println(counts); // {3=2, 4=1, 5=1, 7=1, 8=1, 9=1}
long total = IntStream.of(a1).mapToLong(x -> counts.getOrDefault(x, 0L)).sum();
System.out.println(total);  // 4

Of course, instead of using the Stream API you can just as well use regular loops.

kevin ternet · Answer 2 · 2019-11-28T14:50:52.610

Theres no need of loop to obtain what you want

ArrayList<Integer> l1 = new ArrayList<Integer>();
    l1.add(1);
    l1.add(2);
    l1.add(3);
    l1.add(4);
    l1.add(5);
    ArrayList<Integer> l2 = new ArrayList<Integer>();
    l2.add(9);
    l2.add(5);
    l2.add(4);
    l2.add(3);
    l2.add(8);
    l2.add(3);
    l2.add(7);

    ArrayList<Integer> lFiltered = new ArrayList<Integer>(l2);
    lFiltered.removeAll(l1);

    int Times = l2.size() - lFiltered.size();
    System.out.println("number of migrants : " + Times);

Suffice it to to generate from l2 a list without elements and l1 and to count elements which have been removed

dancingbush · Answer 3 · 2019-11-28T14:51:24.840

Use ArrayLists. To compare the content of both arrays:

ArrayList<String> listOne = new ArrayList<>(Arrays.asList(yourArray1);

        ArrayList<String> listTwo = new ArrayList<>(Arrays.asList(yourArray);

        listOne.retainAll(listTwo);

        System.out.println(listOne)

To find missing elements:

    listTwo.removeAll(listOne);

    System.out.println(listTwo);

To enumerate the Common elements:

//Time complexity is O(n^2)

    int count =0;
    for (String element : listOne){
      for (String element2: listTwo){
       if (element.equalsIgnoreCase(elemnt2){
     count += 1;
    }
    }
    }

Arraylist Comparison using one loop

3 Answers3