数据结构【数组】（二）：查找数组中第二小的元素

谁借莪１个温暖的怀抱￠ 2022-03-06 05:26 236阅读 0赞

## 1、思路简述 ##

### 1.1、数组排序 ###

使用排序算法（快排、堆排等），对数组递增排序。排好序的数组，前两个元素就是两个最小的元素，这种方式的时间复杂度取决于排序算法，排序算法效率最高的时间复杂度是O（nlogn）

### 1.2、遍历数组： ###

对数组遍历两次，第一次遍历中找到最小元素，比如为x；第二次遍历中，找到最小的元素并且大于x，这种方法的时间复杂度是O(n)。

## 2、代码实现 ##

此处代码实现，通过一次遍历找到最小的两个数，时间复杂度为 O(n)

/**
         * 在一次遍历中找到最小的两个数，时间复杂度为O(n)
         * 定义一个长度为2的数组，用来存放两个最小的数字，默认两个元素值都为 Integer.MAX_VALUE
         *
         * @param arr 原始数组
         */
        public static Integer method1(int[] arr) {
            //存放最小的两个数值
            Integer[] minNum = new Integer[2];
            //最小数值
            minNum[0] = Integer.MAX_VALUE;
            //第二小数值
            minNum[1] = Integer.MAX_VALUE;
            //遍历数组
            for (int i = 0; i < arr.length; i++) {
                //如果（minNum[0]）预设最小值，大于原数组索引为 i 的元素，则将该元素赋值给 minNum[0]
                //将 minNum[0] 值赋给 minNum[1]（第二最小值）
                if (minNum[0] > arr[i]) {
                    minNum[1] = minNum[0];
                    minNum[0] = arr[i];
                } else if (minNum[1] > arr[i]) {
                    minNum[1] = arr[1];
                }
            }
            return minNum[1];
        }
    
        /**
         * 在一次遍历中找到最小的两个数，时间复杂度为O(n)
         * <p>
         * 初始化2个最小值:min1、min2
         * 遍历所有元素,如果当前元素小于min1,那么将更新 min1、min2.如果大于 min1 小于 min2 直接更新 min2
         */
        public static int method2(int[] arr) {
            int min1; //存储最小的数值
            int min2; //存储第二小的数值
    
            //判断前两个大小
            if (arr[0] >= arr[1]) {
                min2 = arr[0];
                min1 = arr[1];
            } else {
                min2 = arr[1];
                min1 = arr[0];
            }
            for (int i = 2; i < arr.length; i++) {
                //比最小值小的情况
                if (arr[i] < min1) {
                    min2 = min1;
                    min1 = arr[i];
                }
                //大于最小值且小于第二最小值
                if (arr[i] > min1 && arr[i] < min2) {
                    min2 = arr[i];
                }
            }
            return min2;
        }