查找整数数组中乘积最大的数对

2024年9月10日 | 阅读 6 分钟

在使用 Java 整数数组时，我们可能需要在各种场景下找到乘积最大的数对。这项任务在解决优化问题、最大化效率，甚至在数学背景下寻找可能的最大乘积时都至关重要。在本节中，我们将探讨使用 Java 编程高效处理此问题的各种方法。

方法 1：蛮力法

在整数数组中查找乘积最大的数对的最简单方法是遍历所有可能的数对并计算它们的乘积。我们可以从第一个元素开始，将其与后续的每个元素相乘，并在遇到更高的值时更新最大乘积。这种蛮力法保证能找到乘积最大的数对，但其时间复杂度为 O(n^2)，对于大型数组来说效率不高。

MaxProductPair.java

import java.util.*;
public class MaxProductPair {
    public static void main(String[] args) {
        int[] arr = {2, 3, -4, 5, -6};
        int[] maxPair = findMaxProductPair(arr);
        if (maxPair != null) {
            System.out.println("Maximum product pair: " + maxPair[0] + " and " + maxPair[1]);
            System.out.println("Maximum product: " + (maxPair[0] * maxPair[1]));
        } else {
            System.out.println("No pair found.");
        }
    }
    public static int[] findMaxProductPair(int[] arr) {
        int n = arr.length;
        if (n < 2) {
            return null; // Return null for arrays with less than 2 elements
        }
        int maxProduct = Integer.MIN_VALUE;
        int[] maxPair = new int[2];

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int product = arr[i] * arr[j];
                if (product > maxProduct) {
                    maxProduct = product;
                    maxPair[0] = arr[i];
                    maxPair[1] = arr[j];
                }
            }
        }
        return maxPair;
    }
}

输出

Maximum product pair: -4 and -6
Maximum product: 24

在此代码中，findMaxProductPair 函数遍历数组中的所有可能数对，并跟踪找到的最大乘积。它将乘积最大的数对作为包含两个元素的数组返回。如果找不到这样的数对（例如，如果数组的元素少于两个），则返回 null。

时间复杂度为 O(N^2)，其中 N 是数组中的元素数量。如果数组很大，此方法可能效率不高。存在时间复杂度更好的优化方法，但此蛮力解决方案为查找最大乘积数对提供了一个简单直接的实现。

方法 2：排序

另一种方法是对数组进行非递减排序。一旦数组排序，我们就可以将最后两个元素（绝对值最大的两个元素）视为乘积最大的数对。此方法适用于包含正整数的数组。我们可以将这两个数字相乘以获得最大乘积。此方法的时间复杂度为 O(nlogn)，因为涉及排序操作。

MaxProductPairSorting.java

import java.util.Arrays;
public class MaxProductPairSorting {
    public static void main(String[] args) {
        int[] arr = {2, 3, -4, 5, -6};
        int[] maxPair = findMaxProductPair(arr);
        if (maxPair != null) {
            System.out.println("Maximum product pair: " + maxPair[0] + " and " + maxPair[1]);
            System.out.println("Maximum product: " + (maxPair[0] * maxPair[1]));
        } else {
            System.out.println("No pair found.");
        }
    }
    public static int[] findMaxProductPair(int[] arr) {
        int n = arr.length;
        if (n < 2) {
            return null; // Return null for arrays with less than 2 elements
        }
        // Sort the array in ascending order
        Arrays.sort(arr);
        // Compare the product of the smallest and second smallest with the largest and second largest
        int product1 = arr[0] * arr[1]; // product of the smallest and second smallest
        int product2 = arr[n - 1] * arr[n - 2]; // product of the largest and second largest
        // Choose the larger product
        if (product1 > product2) {
            return new int[]{arr[0], arr[1]};
        } else {
            return new int[]{arr[n - 1], arr[n - 2]};
        }
    }
}

输出

Maximum product pair: -4 and -6
Maximum product: 24

我们有一个整数数组，称之为 arr。

我们的目标是从该数组中找到一个数对，其乘积最大。

我们首先按升序对数组进行排序。这将从最小到最大的顺序重新排列元素。
对数组排序后，前两个元素 (arr[0] 和 arr[1]) 将是最小的两个元素，最后两个元素 (arr[n - 1] 和 arr[n - 2]) 将是最大的两个元素，其中 n 是数组的大小。
最小两个元素的乘积将是 arr[0] * arr[1]，最大两个元素的乘积将是 arr[n - 1] * arr[n - 2]。
为了找到乘积最大的数对，我们比较上一步得到的两个乘积。
两者中较大的乘积将代表乘积最大的数对。

让我们用同一个例子来说明这种方法

示例：考虑数组 arr = {2, 3, -4, 5, -6}。

按升序排序数组：arr = {-6, -4, 2, 3, 5}。
最小的两个元素是 -6 和 -4，它们的乘积是 -6 * -4 = 24。
最大的两个元素是 3 和 5，它们的乘积是 3 * 5 = 15。
由于 24 大于 15，乘积最大的数对是 {-6, -4}，最大乘积为 24。

方法 3：优化方法

为了处理包含负整数的数组，我们需要考虑一种优化方法。我们可以找到数组中的最大和最小元素，然后检查哪对数乘积最大。为此，我们可以遍历数组并跟踪遇到的最大和最小乘积。通过比较最大元素与最小元素的乘积以及反之，我们可以确定乘积最大的数对。

以下是优化方法的 Java 实现

MaximumProductPair.java

public class MaximumProductPair {
    public static void main(String[] args) {
        int[] array = {1, -2, 3, -4, 5, -6};
        int maxProduct = findMaxProductPair(array);
        System.out.println("Maximum product pair: " + maxProduct);
    }
    private static int findMaxProductPair(int[] array) {
        // Initialize variables to store the maximum and minimum elements
        int maxProduct = Integer.MIN_VALUE; // Initialize with the smallest possible value
        int max1 = Integer.MIN_VALUE; // Maximum element
        int max2 = Integer.MIN_VALUE; // Second maximum element
        int min1 = Integer.MAX_VALUE; // Minimum element
        int min2 = Integer.MAX_VALUE; // Second minimum element
        // Iterate through the array to find the maximum and minimum elements
        for (int num : array) {
            // Update the maximum and second maximum elements
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }
            // Update the minimum and second minimum elements
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        // Calculate the maximum product by comparing the products of the maximum and minimum pairs
        maxProduct = Math.max(maxProduct, max1 * max2); // Compare the product of the maximum pair
        maxProduct = Math.max(maxProduct, min1 * min2); // Compare the product of the minimum pair
        return maxProduct;
    }
}

输出

Maximum product pair: 24

解释

给定的数组是 {1, -2, 3, -4, 5, -6}。算法通过将最大乘积 (maxProduct) 初始化为最小值开始。然后，它遍历数组以查找最大和最小元素。

在每次迭代中，算法将当前元素 (num) 与当前最大值 (max1) 和第二大值 (max2) 进行比较。如果 num 大于 max1，则更新 max1 并将之前的 max1 值移至 max2。如果 num 不大于 max1 但大于 max2，则更新 max2。

同样，算法将 num 与当前最小值 (min1) 和第二小值 (min2) 进行比较。如果 num 小于 min1，则更新 min1 并将之前的 min1 值移至 min2。如果 num 不小于 min1 但小于 min2，则更新 min2。

遍历完整个数组后，算法通过比较最大数对的乘积 (max1 * max2) 和最小数对的乘积 (min1 * min2) 来计算最大乘积。最后，它返回最大乘积。

在这种情况下，乘积最大的数对是 (-2) * (-4) = 8。因此，输出为 Maximum product pair: 8。

在 Java 编程中，在整数数组中查找乘积最大的数对是一个常见问题。通过采用不同的方法，如蛮力法、排序或优化方法，我们可以有效地解决此问题。根据数组的特性，选择的方法可能有所不同。了解问题的要求和约束以选择最合适的解决方案至关重要。

下一个主题Java 中的目标堆栈规划程序

查找整数数组中乘积最大的数对

方法 1：蛮力法

方法 2：排序

方法 3：优化方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

查找整数数组中乘积最大的数对

方法 1：蛮力法

方法 2：排序

方法 3：优化方法

相关帖子

Top 10 Java Books

DecimalFormat getMaximumIntegerDigits() method in Java

How do you swap two string variables without using third or temp variable in java

Java Program to Find Largest of Three Numbers

Java Program to Calculate Area and Circumference of Circle

Java 中的单例模式和静态类之间的区别

Java 中的随机访问接口

Java 10 Collectors 方法

Java 中的 java.net.MulticastSocket 类

Java 包注解

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器