How to reduce search complexity in a two-list algorithm?

Question

I need to find some common elements in two lists. I can't sort , order is important. Find the number of secondList elements in firstList . Now it looks like this:

 int[] firstList; int[] secondList; int iterator=0; for(int i:firstList){ while(i <= secondList[iterator]/* two conditions more */){ iterator++; //some actions } } 

The complexity of this algorithm is nxn . I am trying to reduce the complexity of this operation, but I do not know how to compare elements in different ways? Any tips?

EDIT: Example: A=5,4,3,2,3 B=1,2,3 We are looking for pairs B[i],A[j] State: when

 B[i] < A[j] j++ 

when

 B[i] >= A[j] return B[i],A[j-1] 

next iteration through list A to element j-1 (average for(int z=0;z<j-1;z++) ) I'm not sure, I understand? Duplicates allowed.

Answer 1

My approach would be to put all the elements from the first array into a HashSet , and then iterate over the second array. This reduces complexity to the sum of the lengths of two arrays. It has the drawback of using extra memory, but if you are not using more memory, I don’t think you can improve your solution for brute force.

EDIT: to avoid further debate on this issue. If you are allowed to have duplicates in the first array, and you really care about how many times the element in the second array matches the array in the first, use HashMultiSet .

Answer 2

• Put all the elements of the first list into a set
• For each item in the second list, check it in the set.

Solved less than nxn!

Edit to like fge :)

Instead of typing, you can use a map with the element as a key and the number of occurrences as a value.

Then, for each element of the second list, if it exists on the map, perform its action once for each occurrence in the first list (the meaning of dictionary data).

Answer 3

 import java.util.*; int[] firstList; int[] secondList; int iterator=0; HashSet hs = new HashSet(Arrays.asList(firstList)); HashSet result = new HashSet(); while(i <= secondList.length){ if (hs.contains( secondList[iterator])) { result.add(secondList[iterator]); } iterator++; } 

Result

will contain the required common element. Algorithm complexity n

Answer 4

Just because order is important doesn't mean you can't sort the list (or both). This means that you will have to copy first before you can sort anything. Of course, additional memory is required for copying, and sorting requires additional processing time ... but I think that for all solutions that are better than O (n ^ 2), additional memory and processing time will be required (which is also true for the proposed ones) HashSet solutions - adding all values ​​to a HashSet costs extra memory and processing time).

Sorting both lists is possible in O (n * log n) time; searching for common items after sorting lists is possible in O (n) time. Whether it will be faster than your own approach O (n ^ 2) depends on the size of the lists. In the end, only testing different approaches can tell you which approach is the fastest (and these tests should use realistic list sizes, as expected in your final code).

The Big-O designation is not a designation that tells you anything about absolute speed, it only tells you about relative speed. For instance. if you have two algorithms for calculating the value from the input set of elements, one is O (1) and the other is O (n), this does not mean that the solution O (1) is always faster. This is a big misconception of Big-O notation! This means that if the number of input elements doubles, then the solution O (1) will take approx. same amount of time, while O (n) solution takes approx. twice as much time as before. Therefore, there is no doubt that, by constantly increasing the number of input elements, there must be a point where the solution O (1) becomes faster than the solution O (n), but for a very small set of elements O (1) the solution can actually be slower, than the solution O (n).

Answer 5

OK, so this solution will work if there are no duplicates in the first or second array. Since the question does not speak, we cannot be sure.

First, build a LinkedHashSet<Integer> from the first array and a HashSet<Integer> from the second array.

Secondly, save in the first set only those elements that are in the second set.

Thirdly, iterating over the first set and continuing:

 // A LinkedHashSet retains insertion order Set<Integer> first = LinkedHashSet<Integer>(Arrays.asList(firstArray)); // A HashSet does not but we don't care Set<Integer> second = new HashSet<Integer>(Arrays.asList(secondArray)); // Retain in first only what is in second first.retainAll(second); // Iterate for (int i: first) doSomething();