Java 中两组大小之间的最小差异

2024年9月26日 | 阅读 5 分钟

给定一个包含各种数字的数组。任务是创建不同的组，每个组只包含两个元素，使得包含最大和的组与包含最小和的组之间的差异最小。请注意，任何元素只能属于一个组。此外，不允许遗漏任何元素。换句话说，一个元素必须是一个组的一部分。

示例 1

输入

int arr[] = {5, 0, 9, 7, 15, 11, 19, 17}

输出 3

解释： 让我们为给定数组形成一个两个元素的组。

G1 = {5, 17}, G2 = {0, 19}, G3 = {9, 11}, G4 = {7, 15}。如果我们找出每个组中元素的和，我们得到，

G1 = 5 + 17 = 22, G2 = 0 + 19 = 19, G3 = 9 + 11 = 20, G4 = 7 + 15 = 22

因此，我们看到最小和是 19，最大和是 22。因此，差异是 22 - 19 = 3。

示例 2

输入

int arr[] = {4, 11, 5, 3, 7, 2}

输出 4

解释： 让我们为给定数组形成一个两个元素的组。

G1 = {4, 5}, G2 = {11, 2}, G3 = {3, 7}。如果我们找出每个组中元素的和，我们得到，

G1 = 4 + 5 = 9, G2 = 11 + 2 = 13, G3 = 3 + 7 = 10。

因此，我们看到最小和是 9，最大和是 13。因此，差异是 13 - 9 = 4。

示例 3

输入

int arr[] = {4, 9, 3, 8, 2, 0, 5}

输出： 无法找到最小差异。

解释： 让我们为给定数组形成一个两个元素的组。

G1 = {4, 9}, G2 = {3, 8}, G3 = {2, 0}。因此，我们看到我们遗漏了元素 5，根据条件，不允许遗漏任何元素。无论我们如何努力形成不同的组，其中一个元素都必须跳过。因此，该解决方案是不可能的。

方法

方法很简单。必须将最大值保持在最小值，将最小值保持在最大值，以便最大值和最小值之间的差距最小。为了做到这一点，我们必须以最大元素与最小元素配对，第二大元素与第二大元素配对的方式组合数组中的数字。为了实现这一点，需要对数组进行排序，然后将最后一个元素与第一个元素、倒数第二个元素与第二个元素等进行组合（组成一个组）。以下程序中提到了相同的示例。

文件名： LeastDiff.java

// important import statement
import java.util.Arrays;
import java.util.ArrayList;

// Main class
public class LeastDiff
{

// method for computing the minimum between a and b
private int findMin(int a, int b)
{
if(a > b)
{
    return b;
}

return a;
}

// method for computing the maximum between a and b
private int findMax(int a, int b)
{
if(a > b)
{
    return a;
}

return b;
}

// a method that finds the minium difference 
// between the group of two elements
public int findMinDiff(int arr[], int s)
{
    if(s % 2 != 0)
    {
        return -1;
    }
    Arrays.sort(arr);
    int diff = Integer.MAX_VALUE;
    ArrayList<Integer> al = new ArrayList<Integer>();
    for(int i = 0, j = s - 1; i < j; j--, i++)
    {
        // find the sum of the two elements and 
        // add it in to the array list
        al.add(arr[i] + arr[j]);
    }
    
    // for storing the minimum value
    int min = Integer.MAX_VALUE;
    
    // for storing the maximum value
    int max = Integer.MIN_VALUE;
    
    // computing the size
    int size = al.size();
    
    for(int i = 0; i < size; i++)
    {
        // finding the maximum and the minimum
        // among the group of two elements
        min = findMin(min, al.get(i));
        max = findMax(max, al.get(i));
    }
    
    return (max - min);
}
    
// Main method
public static void main(String[] argvs) 
{
// creating an object of the class LeastDiff
LeastDiff obj = new LeastDiff();

// input 1
int arr[] = {5, 0, 9, 7, 15, 11, 19, 17};
int size = arr.length;

System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
    System.out.print(arr[i] + " ");
}
System.out.println();

int ans = obj.findMinDiff(arr, size);

if(ans != -1)
{
System.out.println("The minimum difference is: " + ans);
}
else
{
System.out.println("It is not possible to find the minimum difference.");
}

System.out.println("\n");

// input 2
int arr1[] = {4, 11, 5, 3, 7, 2};
size = arr1.length;

System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
    System.out.print(arr1[i] + " ");
}
System.out.println();

ans = obj.findMinDiff(arr1, size);


if(ans != -1)
{
System.out.println("The minimum difference is: " + ans);
}
else
{
System.out.println("It is not possible to find the minimum difference.");
}
System.out.println("\n");

// input 3
int arr2[] = {4, 9, 3, 8, 2, 0, 5};
size = arr2.length;

System.out.println("For the input array: ");
for(int i = 0; i < size; i++)
{
    System.out.print(arr2[i] + " ");
}
System.out.println();

ans = obj.findMinDiff(arr2, size);


if(ans != -1)
{
System.out.println("The minimum difference is: " + ans);
}
else
{
System.out.println("It is not possible to find the minimum difference.");
}
System.out.println("\n");

}
}

输出

For the input array: 
5 0 9 7 15 11 19 17 
The minimum difference is: 3


For the input array: 
4 11 5 3 7 2 
The minimum difference is: 4


For the input array: 
4 9 3 8 2 0 5 
It is not possible to find the minimum difference.

复杂度分析： 由于程序使用排序，因此程序的时间复杂度为 O(n * log(n))。此外，程序使用数组列表来存储和。因此，程序的空间复杂度为 O(n)，其中 n 是输入数组中存在的元素总数。

下一个主题Java 中等差数列中缺失的数字

← 上一个下一个 →

Java 中两组大小之间的最小差异

方法

联系信息

关注我们

教程

面试题

在线编译器

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 程序

Java 中两组大小之间的最小差异

方法

相关帖子

Java 从单链表末尾删除节点的程序

Java 从双向链表开头删除新节点的程序

Java 从三叉树创建双向链表的程序

查找给定矩阵中奇数和偶数出现频率的 Java 程序

Evil Number Java

Java 中的二分搜索

查找字符串中最大和最小单词的 Java 程序

How to Create Object in Java

ISBN Number Java

Java 中的插入排序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器