数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Java程序查找数组中差值最大的两个元素
在这个问题中，我们将使用Java查找数组中差值最大的两个元素。
我们可以为每个元素创建一个组合，并找出每对元素之间的差值。之后，我们可以选择差值最大的那对元素。另一种方法是排序数组，然后取数组中最大和最小的元素。
问题陈述
我们得到一个包含整数值的数组。我们需要找到两个数组元素，以使它们之间的差值最大化。
输入1
array[] = { 50, 10, 30, 400, 600, 200, 70, 90, 80, 322 }
输出1
The maximum difference between 600 and 10 is 590.
输入2
array[] = {1000, 30, 5000, 476, 987, 312 }
输出2
The maximum difference is between 30 and 5000.
输入3
array[] = {-70, -150, 40, 500, -90 }
输出3
The smallest element in the array is -150, and the largest element is 500.
不同的方法
以下是查找数组中两个元素的不同方法
使用蛮力法
在这种方法中，我们将创建包含两个数组元素的组合。之后，我们将计算这两个元素的差值，并在需要时更新最大差值。
-
将‘curr_diff’初始化为0，以存储两个元素之间的差值，并将‘max_diff’初始化为第一个和第二个元素的差值。此外，初始化‘first’和‘second’变量以存储差值最大的元素对。
-
从第0个索引开始遍历数组。此外，使用嵌套循环从p + 1索引遍历数组。
-
计算位于pth和qth索引处的数组元素的绝对差值，并将它们存储到curr_diff中。
-
如果curr_diff大于max_diff，则更新max_diff、first和second变量的值。
-
打印最大差值、first和second变量的值。
示例
import java.io.*;
public class Main {
public static void getMaxDiff(int array[], int arr_len) {
// Variable initialization
int curr_diff, max_diff = array[1] - array[0];
int first = array[1], second = array[0];
// Traverse the array and find the difference between each 2 elements
for (int p = 0; p < arr_len; p++) {
for (int q = p + 1; q < arr_len; q++) {
curr_diff = Math.abs(array[p] - array[q]);
// If the difference between two elements is greater than max_diff, update max_diff.
if (curr_diff > max_diff) {
max_diff = curr_diff;
first = array[p];
second = array[q];
}
}
}
System.out.println("Maximum difference is " + max_diff + " between " + first + " and " + second);
}
public static void main(String[] args) {
int array[] = { 50, 10, 30, 400, 600, 200, 70, 90, 80, 322 };
int arr_len = array.length;
getMaxDiff(array, arr_len);
}
}
输出
Maximum difference is 590 between 10 and 600
时间复杂度：O(N^2)，用于创建每个元素的组合。
空间复杂度：O(1)，因为我们不使用任何动态空间。
使用排序
在这种方法中，我们将对数组进行排序。之后，我们可以取排序后数组的第一个和最后一个元素，以获得任意两个数组元素之间的最大差值。
- 首先导入java.io和java.util包的必要类。
- 使用Arrays.sort()方法对数组进行排序。
- 计算nums[arr_len - 1]和nums[0]之间的差值。
- 在输出中打印差值、nums[arr_len - 1]和nums[0]。
示例
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
int nums[] = { 50, 10, 30, 400, 600, 200, 70, 90, 80, 322 };
int arr_len = nums.length;
// sort array
Arrays.sort(nums);
// Get the max difference
int max_diff = nums[arr_len - 1] - nums[0];
// print max difference
System.out.println("Maximum difference is " + max_diff + " between " +nums[0] + " and " + nums[arr_len - 1] );
}
}
输出
Maximum difference is 590 between 10 and 600
时间复杂度：O(NlogN)，用于对数组进行排序。
空间复杂度：O(N)，用于对数组进行排序。
使用优化方法
在这种方法中，我们将遍历数组以查找给定数组中的最大和最小元素。之后，我们可以计算最小和最大元素的差值，这将是最大差值。
-
将maxi和mini初始化为第一个数组元素，以存储最大和最小元素。
-
开始迭代数组。
-
如果当前数组元素超过maxi，则更新maxi。如果当前元素小于mini，则更新mini。
-
计算maxi和mini之间的差值。
-
打印maxi和mini之间的差值，以显示在输出中。
示例
import java.io.*;
public class Main {
public static void getMaxDiff(int array[], int arr_len) {
int maxi = array[0];
int mini = array[0];
// Finding the maximum and minimum element in the array
for (int p = 0; p < arr_len; p++) {
if (array[p] > maxi) {
maxi = array[p];
}
if (array[p] < mini) {
mini = array[p];
}
}
// Getting the maximum difference
int max_diff = maxi - mini;
System.out.println("Maximum difference is " + max_diff + " between " + mini + " and " + maxi);
}
public static void main(String[] args) {
int array[] = { -70, -150, 40, 500, -90 };
int arr_len = array.length;
getMaxDiff(array, arr_len);
}
}
输出
Maximum difference is 650 between -150 and 500
时间复杂度：O(N)，用于遍历数组。
空间复杂度：O(1)，因为我们不使用额外的空间。
我们已经看到了三种查找差值最大的两个元素的方法。只有当我们计算最小和最大数组元素的差值时，才能获得两个数组元素之间的最大差值。就时间和空间复杂度而言，第三种方法提供了最优化的解决方案。
415 次查看
