java - 数组中第三小的元素

<分区>

我写了一个方法来找到数组中第二小的数字而不使用排序。我想我可以扩展相同的逻辑来找到数组中的第三小。但是我意识到它是没那么容易..我的大脑一定是因为 sleep 不足或其他原因而变得困惑..下面是我的 findSecondSmallest 和 findThirdSmallest 代码..有人可以纠正我后面逻辑中的缺陷吗？

public class ArrayElementSelection{
    public static int findSecondSmallest(int[] a){
            int N = a.length;
            int min = 0;
            int secondSmallest = 0;
            for(int i=1;i<N;i++){
                if(a[i] < a[min]){
                    secondSmallest = min;
                    min = i;

                }else if(a[i] < a[secondSmallest]){
                    secondSmallest = i;
                }
            }
            return a[secondSmallest];
        }

    public static int findThirdSmallest(int[] a){
            int N = a.length;
            int min = 0;
            int secondSmallest = 0;
            int thirdSmallest = 0;
            for(int i=1;i<N;i++){
                if(a[i] < a[min]){
                    min = i;
                }else if(a[i] < a[secondSmallest]){
                    secondSmallest = i;
                }else if(a[i]< a[thirdSmallest]){
                    thirdSmallest = i;
                }
            }

            return a[thirdSmallest];
        }

    public static void main(String[] args) {
         int[] a = new int[]{4,2,3,1,5};
         System.out.println(findThirdSmallest(a));
    }
}

>> 4

最佳答案

好吧，让我们清理一下。我们想找到数组中第三小的元素。

    NavigableSet<Integer> min3 = new TreeSet<Integer>();
    //We keep only 3 elements in min3, as soon as the set size grows over 3
    //we remove the last element, which is the max.

    for (int x : array) {
        min3.add(x);
        if (min3.size() > 3) {
            min3.pollLast();
        } 
    }

    if (array.length >= 3) {
        Integer thirdMinimum = min3.pollLast();
        System.out.println(thirdMimimum);
    } else {
       //array must contain at least 3 elements
    }

上面的代码片段找到了第三个唯一的最小值。如果我们保留一个排序的整数列表，而不是一组整数。我们可以找到第三个非唯一最小值。

关于java - 数组中第三小的元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17600030/

上一篇：python - 为什么快速排序算法中变异列表的副作用不好？

下一篇：ios - 将 RGB 值转换为 UIColor？

相关文章：

arrays - 由 J 中的多个子数组组成矩阵

javascript - 在通用树中查找元素

java - 需要解释搜索最小大和的算法

java - 如何在java中的另一个字符串中的特定字符后添加一个字符串？

C编程修改快速排序

java - 将值从内部递归方法传递到外部方法

c# - 我想在整数数组的连续子集中找到公共(public)数字的最大频率

java - 使用某种模式格式化数字

Java代理框架实现强制消息传递的最佳方式

java - 在众多依赖项中优先选择最新的 jar (java)