简介
本篇文章将主要介绍获取数组中最大(小)元素的基本方法,以及其在Java中的几种实现方法。
算法
取得数组中最大(小)元素的基本算法一般都类似于如下所示:
SET MAX to array[0]
FOR i = 1 to array.length - 1
IF array[i] > MAX THEN
SET MAX to array[i]
ENDIF
ENDFOR
对于java而言,这一算法逻辑可以有多种不同的实现方式。但无论如何实现,因为在算法中我们需要检查数组中的每一个元素,所以其时间复杂度都是O(n)
,这里n
指的是数组的长度。
迭代(iteration)实现
public int getMaxWithIteration(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("Input array should not be empty!");
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
return max;
}
递归(recursion)实现
public int getMaxWithRecursion(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("Input array should not be empty!");
}
return getMax(nums, 0, Integer.MIN_VALUE);
}
private int getMax(int[] nums, int currIdx, int currMax) {
if (currIdx >= nums.length) return currMax;
return getMax(nums, currIdx + 1, Math.max(nums[currIdx], currMax));
}
利用Java8的stream方法
public int getMaxWithStream(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("Input array should not be empty!");
}
return Arrays.stream(integers).max().getAsInt();
}
我们甚至可以给这里的max()
函数传入一个自定义的比较函数来实现自定义的比较功能,非常方便,如下面的例子所示。
public class Product {
private String name;
private int price;
public Product(String name, int price) {
this.name = name;
this.price = price;
}
public int getPrice() {
return this.price;
}
public String getName() {
return this.name;
}
public static Product getMostExpensiveProduct(Product[] products) {
return Arrays.stream(products)
.max(Comparator.comparing(Product::getPrice))
.orElseThrow(NoSuchElementException::new);
}
}