CODEWITHSUNDEEP
javacollectionsarraylist
elm
elm

Reputation: 20415

Merge and order Lists

For any two ascending sorted ArrayList<Integer> such as

List<Integer> l1 = new ArrayList<Integer>();
l1.add(1);
l1.add(2);
l1.add(5);
l1.add(10);

and

List<Integer> l2 = new ArrayList<Integer>();
l2.add(1);
l2.add(3);
l2.add(5);
l2.add(11);

how to merge them into an ArrayList<Integer> whose values are

1,1,2,3,5,5,10,11

Update

Realised that Integer oversimplifies the problem; in fact these are lists of class

public class Tuple {
  public boolean isComment;
  public int location;
  public String text;

  public Tuple(boolean isAComment, int aLocation, String aText) {
    isComment = isAComment;
    location = aLocation;
    text = aText;
  }
}

As suggested, a valid solution requires a sorting, where location is first criterion, whether it is a comment is the second criterion.

Upvotes: 0

Views: 52

Answers (2)

Dmitry Ginzburg
Dmitry Ginzburg

Reputation: 7461

Are you implementing merge-sort?

The "bycicle"-way (O(n)):

public List<Integer> merge (List<Integer> l1, List<Integer> l2) {
    List<Integer> result = new ArrayList<>();
    int i1 = 0, i2 = 0;
    while (i1 < l1.size() && i2 < l2.size())
        if (l1.get(i1) < l2.get(i2))
            result.add (l1.get(i1++));
        else
            result.add (l2.get(i2++));
    while (i1 < l1.size())
        result.add (l1.get(i1++));
    while (i2 < l2.size())
        result.add (l2.get(i2++));
    return result;
}

In case of List<Tuples> that wouldn't change much, just make your Tuple Comparable:

public class Tuple implement Comparable <Tuple> {
    public boolean isComment;
    public int location;
    public String text;

    public Tuple(boolean isAComment, int aLocation, String aText) {
        isComment = isAComment;
        location = aLocation;
        text = aText;
    }

    public int compareTo (Tuple that) {
        if (location == that.location)
            return Boolean.compare (isComment, that.isComment);
        else
            return Integer.compare (location, that.location);
    }

}

Then, instead of using < operator, you should use l1.get(i1).compareTo(l2.get(i2)) < 0

Upvotes: 2

Mena
Mena

Reputation: 48404

This answer does not contain code, you'll have to figure it out for yourself.

  1. Add the Lists to one another using addAll.
  2. Sort the Lists using Collections.sort

Upvotes: 4

Related Questions