Java 程序在数组中查找 2 个元素,使得它们之间的差异最大

javaobject oriented programmingprogramming更新于 2024/7/30 18:52:17

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

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

问题陈述 - 我们给出了一个包含整数值的数组。我们需要找到两个数组元素,使它们之间的差异最大化。

示例

输入

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

输出

10, 600

说明

600 和 10 之间的最大差异为 590。

输入

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

输出

30, 5000

说明

最大差值在 30 和 5000 之间。

输入

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

输出

150, 500

说明

数组中最小元素为 -150,最大元素为500。

方法 1

在此方法中,我们将创建包含两个数组元素的对。之后,我们将获取两个元素的差异并根据需要更新最大差异值。

算法

  • 步骤 1 - 用 0 初始化"curr_diff"以存储两个元素之间的差异,"max_diff"用第一个和第二个元素的差异。此外,初始化"first"和"second"变量以存储具有最大差异的元素对。

  • 步骤 2 - 从第 0 个索引开始遍历数组。另外,使用嵌套循环从 p + 1 索引遍历数组。

  • 步骤 3 - 取位于第 p 个和第 q 个索引的数组元素的绝对差,并将其存储到 curr_diff 中。

  • 步骤 4 - 如果 curr_diff 大于 max_diff,则更新 max_diff、第一个和第二个变量的值。

  • 步骤 5 - 打印最大差、第一个和第二个变量的值。

示例

import java.io.*;
public class Main {
   public static void getMaxDiff(int array[], int arr_len) {
      // 变量初始化
      int curr_diff, max_diff = array[1] - array[0];
      int first = array[1], second = array[0];

      // 遍历数组并找出每 2 个元素之间的差异
      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]);
            // 如果两个元素之间的差异大于max_diff,则更新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);
   }
}

输出

10 和 600 之间的最大差异为 590

时间复杂度 – 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;
    
    // 对数组进行排序
    Arrays.sort(nums);
    
    // 获取最大差异
    int max_diff = nums[arr_len - 1] - nums[0];
    
    // 打印最大差异
    System.out.println("" +nums[0] + " 和 " + nums[arr_len - 1] 之间的最大差异为 " + max_diff + " );
   }
}

输出

10 和 600 之间的最大差异为 590

时间复杂度 – 对数组进行排序的复杂度为 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];
      // 查找数组中的最大和最小元素
      for (int p = 0; p < arr_len; p++) {
         if (array[p] > maxi) {
            maxi = array[p];
         }
         if (array[p] < mini) {
            mini = array[p];
         }
      }
      // 获取最大差异
      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)。

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


相关文章


有用资源