Geek asks and answers

Search in ArrayList

I have 2 ArrayLists that have Array of Strings as a “component”. I want to find "components" whose first element is the same in both ArrayLists. To be more clear:

ArrayList One
first component => {"0", "zero"}
second component => {"1", "one"}
ArrayList Two
first component => {"1", "uno"}
second component => {"2", "two"}

I would like to go through ArrayList Two and find {"1", "uno"}. So far, I have a nested loop that goes through the first array, and then checks the current component for each component in ArrayList Two.

    for(int i=0; i<One.size(); i++)
    {
        for(int j=0; j<Two.size(); j++)
        {
            if( fileOne.get(i)[0].equals( Two.get(j)[0] ) )
            {
                System.out.print( Two.get(j)[0]+" " );
                System.out.print( Two.get(j)[1] );
                System.out.println();
            }
        }
    }

I think there should be a better solution. Any help

+3
source share
4 answers

Use a HashSet.

Set<String> set = new HashSet<String>()
for(int i=0; i<One.size(); i++) {
  set.add(fileOne.get(i)[0]);
}

for(int i=0; i<Two.size(); i++) {
  String component[] = Two.get(j)
  if(set.contains(component[0])) {
    System.out.print( component[0]+" " );
    System.out.print( component[1] );
    System.out.println();
   }
}

. , O (N). HashSets - O (1), ( ) - O (N). O (M), O (1).

, O (N) + (O (M) * O (1)) = O (N + M)

: .

+2

hashmap. ArrayList, ( ). ArrayList , ( , , null).

+2

retainAll , :

One.retainAll(Two)

- O (n + m) O (n * m). . , retainAll hashset One, , .

+1

( )

, / / , , O (n * m), . , .

I should also mention that in some scenarios it might be wiser to keep the list sorted. Then, instead of comparing each item, you can use binary search or something else. But first, without sorting your list, yes, you have to compare all the elements. I find the best sorting time is O (nlgn). Then after this sorting process, you still have to search for the sorted list for your item, but searching in a sorted list can be faster than finding an unsorted one.

-1
source

More articles:


All Articles