Нахождение третьего по величине элемента массива путем сортировки его через TreeSet в порядке убывания

Question

Я пытаюсь найти третий по величине элемент массива, сортируя его по древовидной структуре в убывающем порядке, но некоторые тестовые примеры терпят неудачу для определенных входных значений, и большинство из них проходит для определенных входных значений.

Мой код:

// { Driver Code Starts
import java.util.Scanner;
import java.util.*;
import java.io.*;

class ThirdLargestElement
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t>0)
        {
            long n =sc.nextLong();
            Long arr[] = new Long[(int)n];
            for(long i=0;i<n;i++)
                arr[(int)i] = sc.nextLong();
            GfG g = new GfG();
            System.out.println(g.thirdLargest(arr));
        t--;
        }
    }
}// } Driver Code Ends
class GfG
{
    long thirdLargest(Long a[])
    {
    // Your code here
        if(a.length<3)
            return -1;
        else{
            TreeSet<Long> ts=new TreeSet<Long>(new myComparator());
            for(long i:a)
                ts.add(i);
            ArrayList<Long> al=new ArrayList<Long>(ts);
            return al.get(2);
        }
    }
}
class myComparator implements Comparator{
    public int compare(Object obj1,Object obj2){
        Long a=(Long) obj1;
        Long b=(Long) obj2;
        if(a<b)
            return 1;
        else if(a>b)
            return -1;
        else 
            return 0;
    }
}

Тестовый сценарий, в котором он не прошел:

Ссылка на вопрос, где можно запустите код

Пожалуйста, объясните, почему этот код не прошел данный тестовый пример.

Answer 1

Вы можете напрямую добавить элементы к TreeSet и получить третий по величине номер, используя поток,

while(t>0)
{
    long n =sc.nextLong();
    TreeSet<Long> ts=new TreeSet<>(Comparator.comparingLong(Long::longValue).reversed());
    for(long i=0;i<n;i++)
        ts.add(sc.nextLong());
    long thirdLast = ts.stream()
            .limit(3)
            .skip(2)
            .mapToLong(e->e)
            .findAny().orElse(0l);

    System.out.println(thirdLast);
    t--;
}

Answer 2

Вопрос гласит:

функция thirdLargest ... принимает два аргумента. Первым аргументом является массив a [], а вторым аргументом является размер массива (n).

Хотя вопрос гласит, что массив ...

массив различных элементов

тесты показывают, что мы имеем дело с массивом целых чисел.

Лично я не вижу необходимости во втором параметре метода потому что в java массив является объектом и имеет length член. Так что моя реализация ниже принимает только один параметр, а именно массив int. Возможно, люди на geeksforgeeks.org просто преобразовали вопрос, который изначально был для языка C, в java, поскольку в C трудно определить размер любого массива.

Каждый элемент в TreeSet должен быть объектом, поэтому нам нужно преобразовать элементы в массиве int в Integer объекты. Autoboxing сделает это автоматически, тем не менее мой код ниже содержит явное преобразование. Таким образом, в методе я создаю TreeSet. Поскольку класс Integer реализует интерфейс Comparable , достаточно стандартного конструктора TreeSet. Я добавляю все элементы массива int в TreeSet, затем получаю нисходящий итератор и затем перехожу к третьему элементу, возвращенному итератором, который является значением, которое должен возвращать метод.

    int thirdLargest(int[] arr) {
        int third = -1;
        if (arr != null  &&  arr.length > 2) {
            TreeSet<Integer> set = new TreeSet<Integer>();
            for (int elem : arr) {
                set.add(Integer.valueOf(elem));
            }
            Iterator<Integer> iter = set.descendingIterator();
            if (iter.hasNext()) {
                iter.next();
                if (iter.hasNext()) {
                    iter.next();
                    if (iter.hasNext()) {
                        third = iter.next().intValue();
                    }
                }
            }
        }
        return third;
    }

Конечно, если вы хотите игнорировать условия, налагаемые исходным вопросом, вы можете получить третий по величине элемент, используя stream API

IntStream.of(2, 4, 1, 3, 5)
         .boxed()
         .sorted(Collections.reverseOrder())
         .collect(Collectors.toList()).get(2)

Answer 3

Попробуйте это

class GfG {
    long thirdLargest(Long a[]) {
        Arrays.sort(a);
        List<Long> numbers = Arrays.asList(a);
        Collections.reverse(numbers);
        return numbers.size() >= 3 ? numbers.get(2) : -1;
    }
}