CODEWITHSUNDEEP
javaarraylist
cowboysfan1995
cowboysfan1995

Reputation: 3

How can I find the positions of something in an ArrayList in a nested loop?

is there a way to compare two arrayLists to see if either of them have equal values at any point? I know that I can use two nested loops, however I am trying to do this in log(n) time, so instead, I am trying to do it similarly to how one would merge two lists in mergesort, however I can't really figure out exactly how to implement it. Any help would be greatly appreciated! Thanks! Edit: Yeah I meant nlog(n), not log(n), sorry

Upvotes: 0

Views: 76

Answers (4)

Payne
Payne

Reputation: 474

What about Heap? Then just merge that heaps.

Upvotes: 0

UniversE
UniversE

Reputation: 2506

You can't do it in O(log(n)).

You can implement this with O(n*log(n)) by first sorting both list and then comparing them element-wise (sorting takes nlogn and comparing n)

You can do it like this:

  1. create to variables i, j initialized with 0

  2. loop over the lists and compare l1.get(i) with l2.get(j)

3a. equal: increment both i, j (and maybe memorize the tuple)

3b. element of l1 is smaller than the element of l2: increment i only

3c. element of l1 is greater than the element of l2: increment j only

  1. exit loop, if one index is out of bounds

You don't need to scan the list for the index that was not out of bounds, since you are just interested in the equal values.

Upvotes: 1

Thirumalai Parthasarathi
Thirumalai Parthasarathi

Reputation: 4671

if both list are of same size then

for(int i =0; i<listOne.size();i++) {
  int index = listTwo.indexOf(listOne.get(i));
  if(index !=-1) {
    System.out.println("equal at listOne[" + i + "] and listTwo[" +  index + "]");
  }
}

Upvotes: 0

Jon Kiparsky
Jon Kiparsky

Reputation: 7773

If you want to compare whether the values are the same at any point (ie, object at index 1 of list 1 == object at index 1 of list 2) then you'd just loop over the lists and compare (O(N))

If you want to find out whether they have any values in common, sort both and walk down the lists. O (n log n), because of the sorting.

Upvotes: 0

Related Questions