图解|查找数组中最大值的5种方法!

原创
09/16 08:00
阅读数 1.3K

作者 | 王磊

来源 | Java中文社群(ID:javacn666)

转载请联系授权(微信ID:GG_Stone)

我们在一些特定场景下,例如查询公司员工的最高薪资,以及班级的最高成绩又或者是面试中都会遇到查找最大值的问题,所以本文我们就来列举一下查询数组中最大值的 5 种方法。首先我们来看最原始也是最“笨”的实现方法:循环对比和递归对比。

方式一:循环对比

循环对比的执行流程如下图所示:

从上图可以看出,循环对比的核心是定义一个最大值,然后循环对比每一个元素,如果元素的值大于最大值就将最大值更新为此元素的值,再进行下一次比较,直到循环结束我们就能找到最大值了,实现代码如下:

public class ArrayMaxTest {
    public static void main(String[] args) {
        int[] arr = {3721, -4};
        int max = findMaxByFor(arr); // 查找最大值
        System.out.println("最大值是:" + max);
    }

    /**
     * 通过 for 循环查找最大值
     * @param arr 待查询数组
     * @return 最大值
     */

    private static int findMaxByFor(int[] arr) {
        int max = 0// 最大值
        for (int item : arr) {
            if (item > max) { // 当前值大于最大值,赋值为最大值
                max = item;
            }
        }
        return max;
    }
}

以上程序的执行结果为:

最大值是:7

方式二:递归对比

递归对比的核心是先定义两个位置(起始位置和结束位置),每次对比开始位置和结束位置值的大小,当开始位置的值大于结束位置值时,将最大值设置为开始位置的值,然后将结束位置 -1(往前移动一位),继续递归调用;相反,当结束位置的值大于开始位置时,将最大值设置为结束位置的值,将开始位置 +1(往后移动一位),继续递归调用对比,直到递归结束就可以返回最大值了,执行流程如下图所示:


实现代码如下:

public class ArrayMax {
    public static void main(String[] args) {
        int[] arr = {3721, -4};
        int max = findMaxByRecursive(arr, 0, arr.length - 10); // 根据 Collections 查找最大值
        System.out.println("最大值是:" + max);
    }

    /**
     * 根据递归查询最大的值
     * @param arr  待查询数组
     * @param head 最前面的元素的下标
     * @param last 最末尾的元素的下标
     * @param max  (临时)最大值
     * @return 最大值
     */

    private static int findMaxByRecursive(int[] arr, int head, int last, int max) {
        if (head == last) {
            // 递归完了,返回结果
            return max;
        } else {
            if (arr[head] > arr[last]) {
                max = arr[head]; // 赋最大值
                // 从后往前移动递归
                return findMaxByRecursive(arr, head, last - 1, max);
            } else {
                max = arr[last]; // 赋最大值
                // 从前往后移动递归
                return findMaxByRecursive(arr, head + 1, last, max);
            }
        }
    }
}

以上程序的执行结果为:

最大值是:7

方式三:依赖 Arrays.sort() 实现

根据 Arrays.sort 方法可以将数组从小到大进行排序,排序完成之后,取最后一位的值就是最大值了,实现代码如下:

import java.util.Arrays;

public class ArrayMax {
    public static void main(String[] args) {
        int[] arr = {3721, -4};
        int max = findMaxBySort(arr); // 根据 Arrays.sort 查找最大值
        System.out.println("最大值是:" + max);
    }

    /**
     * 根据 Arrays.sort 查找最大值
     * @param arr 待查询数组
     * @return 最大值
     */

    private static int findMaxBySort(int[] arr) {
        Arrays.sort(arr);
        return arr[arr.length - 1];
    }
}

以上程序的执行结果为:

最大值是:7

方式四:根据 Arrays.stream() 实现

stream 是 JDK 8 新增的核心功能之一,使用它我们可以很方便的实现很多功能,比如查找最大值、最小值等,实现代码如下:

import java.util.Arrays;

public class ArrayMax {
    public static void main(String[] args) {
        int[] arr = {3721, -4};
        int max = findMaxByStream(arr); // 根据 stream 查找最大值
        System.out.println("最大值是:" + max);
    }

    /**
     * 根据 stream 查找最大值
     * @param arr 待查询数组
     * @return 最大值
     */

    private static int findMaxByStream(int[] arr) {
        return Arrays.stream(arr).max().getAsInt();
    }
}

以上程序的执行结果为:

最大值是:7

方式五:依赖 Collections.max() 实现

使用 Collections 集合工具类也可以查找最大值和最小值,但在使用之前我们想要将数组(Array)转换成集合(List),实现代码如下:

import org.apache.commons.lang3.ArrayUtils;
import java.util.Arrays;
import java.util.Collections;

public class ArrayMax {
    public static void main(String[] args) {
        int[] arr = {3721, -4};
        int max = findMaxByCollections(arr); // 根据 Collections 查找最大值
        System.out.println("最大值是:" + max);
    }

    /**
     * 根据 Collections 查找最大值
     * @param arr 待查询数组
     * @return 最大值
     */

    private static int findMaxByCollections(int[] arr) {
        List<Integer> list = Arrays.asList(
                org.apache.commons.lang3.ArrayUtils.toObject(arr));
        return Collections.max(list);
    }
}

以上程序的执行结果为:

最大值是:7

扩展知识:Arrays.sort 方法执行原理

为了搞明白 Arrays#sort 方法执行的原理,我们查看了源码发现 sort 方法的核心是通过循环进行排序的,源码如下:

for (int i = left, j = i; i < right; j = ++i) {
 int ai = a[i + 1];
 while (ai < a[j]) {
  a[j + 1] = a[j];
  if (j-- == left) {
   break;
  }
 }
 a[j + 1] = ai;
}

执行流程如下图所示:

总结

本文介绍了 5 种查询数组中最大值的方法,从大的维度可分为:手动实现和依赖接口实现。手动实现主要是通过循环和递归对比的方式,但这种方式并不推荐,因为它不够优雅;依赖接口实现的方法有很多,其中主要推荐使用的是使用 stream 来实现查找最大值,因为它足够简单优雅。


   
   

往期推荐

漫画:什么是红黑树?(整合版)

2020-09-15

万字详解|手撕 9大排序算法!

2020-09-11

字符串操作的12个小技巧!

2020-09-10


关注下方二维码,收获更多干货!

本文分享自微信公众号 - Java中文社群(javacn666)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
2 收藏
分享
加载中
更多评论
打赏
0 评论
2 收藏
0
分享
在线直播报名
返回顶部
顶部