Java 以找到数组中差异最大的两个元素

在这个问题中，我们要找到两个数组元素，使它们之间的差异最大。

我们可以对每个元素进行配对，并找出每对元素之间的差值。然后，我们可以选择差值最大的对。另一种方法是对数组进行排序，然后从数组中选择最大和最小的元素。

问题描述 − 我们已经给出一个包含整数值的数组。我们需要找到两个数组元素，以最大化它们之间的差异。

示例

输入

array[] = { 50, 10, 30, 400, 600, 200, 70, 90, 80, 322 }

输出

10, 600

解释

The maximum difference between 600 and 10 is 590.

输入

array[] = {1000, 30, 5000, 476, 987, 312 }

输出

30, 5000

解释

The maximum difference is between 30 and 5000.

输入

array[] = {-70, -150, 40, 500, -90 }

输出

150, 500

解释

The smallest element in the array is -150, and the largest element is 500.

方法1

在这个方法中，我们将创建包含两个数组元素的对。然后，我们将计算两个元素的差值，并在需要时更新最大差值。

步骤

• 步骤 1 - 将 curr_diff 初始化为0以存储两个元素之间的差值，将 max_diff 初始化为第一个和第二个元素的差值。还要初始化 first 和 second 变量以存储具有最大差值的一对元素。

• 步骤 2 - 从第0个索引开始遍历数组。同时，使用一个嵌套循环从p + 1索引开始遍历数组。

• 步骤 3 - 取数组在第p个和第q个索引处的元素的绝对差值，并将它们存储到curr_diff中。

• 步骤 4 - 如果curr_diff大于max_diff，则更新max_diff，first和second的值。

• 步骤 5 - 打印最大差值，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)。

方法2

在这个方法中，我们将对数组进行排序。然后，我们可以取排序后数组的第一个和最后一个元素来获取任意两个数组元素之间的最大差值。

步骤

• 步骤1 - 使用Arrays.sort()方法对数组进行排序。

• 步骤2 - 取nums[arr_len – 1]和nums[0]之间的差值。

• 步骤3 - 将差值、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)，用于排序数组。

方法3

在这种方法中，我们将遍历数组以找出给定数组的最大和最小元素。然后，我们可以取最小和最大元素的差值，这将是最大差值。

步骤

• 第1步 - 使用第一个数组元素初始化maxi和mini，以存储最大和最小元素。

• 第2步 - 开始迭代数组。

• 第3步 - 如果当前数组元素超过maxi，则更新maxi。如果当前元素小于mini，则更新mini。

• 第4步 - 取maxi和mini之间的差值。

• 第5步 - 打印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)，因为我们不使用额外的空间。

我们已经看到了三种找到最大差异的两个元素的方法。只有当我们取最小和最大的数组元素之间的差异时，才能获得两个数组元素之间的最大差异。第三种方法提供了最优化的解决方案，从时间和空间复杂性的角度来看。