2

Great suggestions but some of them were not allowed (as streams), was very restricted task. Leo's algorithm was the thing I was looking for.

I'm trying to compare a specific letter on arraylist elements and need to remove every bigger letter from the arraylist. This has to be done in linear time, so remove() is not an option. How do I do it?

int deleted = 0;
int n = 0;

while (n < A.size()) {
    if (A.get(n).compareTo(x) > 0) {
        //removing here
        removed = removed + 1;
    }
    n++;
}

return removed;

A is an arraylist with random alphabetical letters and x is also a random letter. I need to remove every element from A which is bigger than the given x letter. Remove() is not an option because I need to do this in linear time instead of n^2.

Improve this question
8
  • Is the list sorted? Commented Sep 14, 2019 at 15:05
  • @WillemVanOnsem No it is not sorted and I cant sort it. Commented Sep 14, 2019 at 15:07
  • 1
    Please add a real minimal reproducible example, with example data that we can ideally run to repro the problem you intend to solve. Commented Sep 14, 2019 at 15:07
  • @Dici this is homework and im insisted to use arraylist Commented Sep 14, 2019 at 15:07
  • 1
    @k5_: an ArrayList has a dynamic size, and the amortized cost makes adding n elements linear (see cs.stackexchange.com/questions/63752/…) hence, it is sufficient to simply add elements. Commented Sep 14, 2019 at 15:09

5 Answers 5

Reset to default
3

You can add elements in linear time to another list. For example:

ArrayList<Integer> result = new ArrayList<Integer>();
for(int n = 0; n < A.size(); n++) {
    if(A.get(n).compareTo(x) <= 0) {
        result.add(A.get(n));
    }
}
return result;

or with streams as @Dici says:

A.stream().filter(n -> n.compareTo(x) <= 0).collect(Collectors.toList());

You can later swap the lists, or clear the original list, and copy the values from result back in that list, which takes linear time as well.

Although using another data structure to store data might be beneficial as well.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

You could also fhow the solution using streams, it's neater! Also, to my knowledge no version of Java supports primitive generics although they want to do it eventually.
1

We can use a SortedSet to get the set having elements less than the given string, this can be achieved by using the SortedSet.headSet(String key) method:

List<String> list = new ArrayList<>();
list.add("d");
list.add("l");
list.add("e");
list.add("z");
list.add("x");

SortedSet<String> set = new TreeSet<>(list);
String x = "f"; //string to compare
List<String> elementsLessThanX = new ArrayList<>(set.headSet("f")); 
System.out.println(elementsLessThanX);

Output:

[d, e]

This is definitely not constant time but it is better than O(n^2). This implementation would not modify the original list.

Improve this answer

Comments

1

Maybe that's you need? 

ArrayList<String> b = a.stream().filter(l -> l.compareTo(x) <= 0)
                                .collect(Collectors.toCollection(ArrayList::new));
Improve this answer

1 Comment

It's not doing the right thing, the OP wants to remove all elements larger than a given character, not those that are different from it
1

The least expensive solution is to traverse the list once while incrementing an index that represents the number of elements matching the criterion. Every time an element is found, it is set at this index and the index is incremented. In the end, you just have to delete everything at the right of this index. It's cheap to do so because deleting at the end of an array list is constant time.

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>(Arrays.asList(1, 3, 6, 4, 7, 0, 2));
    filterLargerElementsInPlace(list, 4, Comparator.naturalOrder());
    System.out.println(list); // [1, 3, 0, 2]
}

public static <T> void filterLargerElementsInPlace(List<T> list, T max, Comparator<T> cmp) {
    int i = 0;
    for (T elem : list) {
        if (cmp.compare(elem, max) < 0) {
            // mutating the list as we traverse it, but it's safe as i is always less than the current index
            list.set(i++, elem);
        }
    }
    while (list.size() > i) list.remove(list.size() - 1);
}
Improve this answer

Comments

0

If you want to remove elements in linear time from the list itself rather than creating a new list, then you can do it like this.

int i = 0;
int j = 0;

while (j < A.size()) {
    if (A.get(j).compareTo(x) > 0) {
        j++;
    } else if (i < j) {
        A.set(i++, A.get(j++));
    } else {
        i++;
        j++;
    }
}
int oldSize = A.size();
int newSize = oldSize - j + i;
A.subList(newSize, oldSize).clear();

This basically runs once through the list, shifting down elements to overwrite the elements that need to be filtered out. Then the list is trimmed down to size in the last three lines.

Improve this answer

3 Comments

Just if you're interested, check my implementation. It's the same idea but perhaps a bit neater.
@Dici your implementation won't always work, because some lists will throw an exception if you modify them while running through them with an Iterator (as your for-each loop does).
I tested it on an array list, sounds ok. Worst-case scenario the same can be done using a for i ... loop, I don't think any list would complain about that. To be fair this implementation only works well on random access lists, I didn't try to make it good for any list. But in the general case, you might be right. Are you aware of any standard list implementation that wouldn't like this?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.