通过按降序对 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;
    }
}

失败的测试用例：

Link to the question where you can run the code

请解释此代码未能通过给定测试用例的原因。

Answer 1

可以直接向TreeSet添加元素，使用stream获取第三大数，

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

试试这个

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;
    }
}

Answer 3

question 状态：

the function thirdLargest ... takes two argument. The first argument is the array a[] and the second argument is the size of the array (n).

尽管问题表明数组是...

an array of distinct elements

测试用例表明我们正在处理一个整数数组。

就我个人而言，我认为不需要第二个方法参数，因为在 java 中，数组是一个对象并且有一个 length 成员。所以我下面的实现只需要一个参数，即int的数组。可能geeksforgeeks.org的人只是简单的把一个原本是C语言的问题改成了java，因为在C中，很难判断大小任何数组。

TreeSet中的每个元素都必须是一个对象，所以我们需要将int数组中的元素转换为Integer个对象。 Autoboxing will do this automatically, nonetheless my code below contains an explicit conversion. So in the method I create a TreeSet. Since class Integer implements interface Comparable，默认的TreeSet构造函数就足够了。我将 int 数组的所有元素添加到 TreeSet 中，然后得到一个降序迭代器，然后迭代到迭代器 return 的第三个元素，这是该方法的值需要 return.

    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)

通过按降序对 TreeSet 进行排序来查找数组的第三大元素

Finding the third largest element of an array by sorting it through TreeSet in a decreasing order

java

arraylist

comparator

testcase

treeset