专栏首页国产程序员寻找数组中第二小的元素

寻找数组中第二小的元素

方法一:用选择排序,冒泡法,或者交换排序这类的排序 先把数组进行升序排序 排完序后再进行遍历比较。排序算法中效率最高的时间复杂度为O(nlnogn)

 public static void main(String[] args) {
        int arr[]={-4,-4,56,34,76,34,23,4,75,87,50,3,5,6,};

        //冒泡排序
        for(int i=0;i<(arr.length)-1;i++){
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        int secondNum=arr[0];
        for (int i=0;i<arr.length;i++){
            if(arr[i]>secondNum){
                secondNum=arr[i];
                break;
            }
        }
        System.out.println("secondNum---->"+secondNum);
    }

方法二:遍历数组,找出最小的两个数字。时间复杂度为O(n)

public static void main(String[] args) {

        int arr[]={-87,-97,23,90,12,-87,-87};

        int firstmin = Integer.MAX_VALUE;   //第一小的元素  初始值设为int的最大取值
        int secondmin = Integer.MAX_VALUE;   //第二小的元素  初始值设为int的最大取值

        for(int value:arr){
            if (value < firstmin) //小于最小的元素 更新1和2
            {
                secondmin = firstmin;
                firstmin = value;
            }
            else if (value < secondmin && value != firstmin) //小于倒数二的 更新2
            {
                secondmin = value;
            }
        }
        System.out.println("firstmin--------->"+firstmin);
        System.out.println("secondmin--------->"+secondmin);
}

方法三:用快速排序的思想。算法复杂度是O(N)

 public static void main(String[] args) {

        int arr[]={34,12,23,90,12,-87,-27};
        Arrays.sort(arr);  //排序  升序
        int secondNum=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[0]<arr[i]){
                secondNum=arr[i];
                break;
            }
        }
        System.out.println(secondNum);
}

方法四:第四种方法很是简单,但是使用它需要某个条件,也就是输入数组的取值范围很小,最好的情况是能形成完全分布,也就是1000大小的数组里面的数字是从1到1000这样子。首先,生成一个能够完全装下原数组的数组,这个地方的装下是指数组大小等于原数组最大元素(也许还有优化,但这么描述简单一点),比如原数组是[1,2,3,4,5],我要生成的数组大小是5,如果原数组是[5,3,6,10],我要生成的数组大小是10。接下来遍历原数组,把每一个元素放到第二个数组对应的下标处,5就放在下标为5的地方(实际过程中要减1,因为是数组从0开始)。放的过程中增加元素值用来统计这个元素出现的次数。这一过程算法复杂度是O(N)。接下来,再遍历生成的数组,找出第K大的元素。这个过程的算法复杂度是多少呢?其实这个和原数组很有关系,原数组越离散也就越糟糕。比如原数组是[1,1000],这样就十分糟糕。第二部的算法复杂度是O(M),M是前数组的最大值。总的算法复杂度O(N)+O(M); 方法五:第五种方法是用二叉堆来做。对大小为N的数组构建二叉堆的算法复杂度是O(N)。然后每次下滤的算法复杂度是O(logN),一共下滤K次,算法复杂度是O(N+K*logN)。这种做法比较适合用来处理输入数组极大的情况,原因是如果输入数组大到不能放入内存,那么构建二叉堆(优先队列)的时候就可以只构造一个K个元素的优先队列。如果下一个元素比这个最大堆的堆顶还大就直接pass。第二个原因是算法二在对付一个极大的输入队列的时候算法复杂度的一个常数会很大。

本文分享自微信公众号 - 国产程序员(Monday_lida),作者:看似无限透明的你

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 记一次jsoup的使用

    connect(String url) 方法创建一个新的 Connection, 和 get() 取得和解析一个HTML文件。如果从该URL获取HTML时发生错...

    一觉睡到小时候
  • Oracle中的正则表达式(及函数)详解

    在介绍函数前,这里先说明一下Oracle中正则表达式运算符及其描述。 如果不知道他们有什么用,或者也不知道描述说的是什么,没关系,可以先看后面的介绍,就知道他们...

    一觉睡到小时候
  • 面向对象的7种设计原则(4)-合成/聚合复用原则

    在一个新的对象里面使用一些已有的对象,使之成为新对象的一部分;新的对象通过向这些对象的委派达到复用这些对象的目的。

    一觉睡到小时候
  • java基础学习_基础语法(下)01_day05总结

    ============================================================================= ==...

    黑泽君
  • 如何实现归并排序?

    划分步骤很简单:将当前数组分成两半(如果N是偶数,则将其完全平等,或者如果N是奇数,则一边稍大于一个元素),然后递归地对这两半进行排序。

    行百里er
  • [算法题] 荷兰国旗问题

    假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况:

    CoderJed
  • 【Java】04 数组

    初始化:   静态初始化:初始化时由程序员显式指定每个数组元素的初始值,由系统决定数组长度。   动态初始化:初始化时程序员只指定数组长度,由系统为数组元素...

    Demo_Null
  • java基础04

    待你如初见
  • 求解连续子数组和全解析-常规解法VS树状数组!

    本文将介绍几求解数组前缀和和连续子数组和的三种方法,分别是遍历法、辅助数组法、树状数组法。

    石晓文
  • LeetCode刷题记录:剑指 Offer 10- I. 斐波那契数列

    解题思路: 根据输入的 n 声明一个数组,定义好数组的前两个元素(即第 0 项和第 1 项),从第三个元素开始遍历数组,使数组的每一个元素等于前两个元素之和。...

    英雄爱吃土豆片

扫码关注云+社区

领取腾讯云代金券