I want to return the X highest numbers from my arrayList. It means that if I have [1, 3, 6, 8, 7, 9], I return 2, so it's going to be [8, 9].

public static void main(String[] args) {

    List<Integer> listA = new ArrayList<>();
    listA.addAll(Arrays.asList(5, 9, 9, 4, 5, 8));
    System.out.println(numbers(listA, 2));

}

public static List<Integer> numbers(List<Integer> intsList, int value) {
    List<Integer> elements = new ArrayList<>();


    return elements;
}

the thing is, that I don't know what kind of logic I can put inside method. I guess I need to iterate through the arrayList on each number > then create highest numbers logic of this arrayList > and return my numbers? Any hints? (not expecting code, just suggestions)

CodePudding user response：

You could sort the list and take the X highest values. With Java's streams, this can even be a single statement:

public static List<Integer> numbers(List<Integer> intsList, int value) {
    return intsList.stream()
                   .sorted(Comparator.reverseOrder())
                   .limit(value)
                   .collect(Collectors.toList());
}

CodePudding user response：

You could possibly sort the number array with the sorting algorithm of your choice and just take the x highest or lowest numbers from either side

More on sorting algorithms: https://stackabuse.com/sorting-algorithms-in-java/

CodePudding user response：

public static void main(String[] args) {

    List<Integer> listA = new ArrayList<>();
    listA.addAll(Arrays.asList(5, 9, 9, 4, 5, 8));
    System.out.println(numbers(listA, 2));
}

public static List<Integer> numbers(List<Integer> intsList, int value) {
    return intsList.stream().distinct()
            .sorted(Comparator.reverseOrder())
            .limit(value)
            .collect(Collectors.toList());
}

we used distinct first to removes the duplicated value.

the result will be:

[9, 8]

CodePudding user response：

return the X highest numbers from an ArrayList.

It means that if I have [1,3,6,8,7,9], I want to return 2 elements, so it's gonna be [8,9].

Firstly, the key point is that this task doesn't require sorting the whole list.

Instead, we can perform partial sorting. By keeping X the largest elements encountered so far. When X is much smaller than the list size, it would result in a considerable performance gain.

PriorityQueue is your new friend

For that, we can maintain a PriorityQueue while iterating over the given list.

At each iteration step, check the size of queue:

• if it's less than X, add the element to the queue;

• if it's equal to X, then compare the lowest element in the queue (it an O(1) operation) with the next element. If the next element is lower or equal - ignore it. Otherwise, remove the lowest element and add the new one.

Implementation might look like that:

public static List<Integer> getHighestX(List<Integer> list, int size) {
    Queue<Integer> queue = new PriorityQueue<>();
    
    for (Integer next: list) {
        if (queue.size() == size && queue.peek() < next) queue.remove(); // removing the lowest element in the queue if queue is full and next is greater
        if (queue.size() < size) queue.add(next);                        // adding the next element if there's a free space in the queue
    }
    
    return new ArrayList(queue);
}