Минимальная абсолютная разница соседних элементов и вычисляемая сумма

Question

Учитывая массив из n целых чисел, переставьте их так, чтобы сумма абсолютных разностей всех элементов была минимизирована, а затем вычислите сумму этих различий.

Пример использования: n = 5, arr = [5,1,3,7,3]

O / P: 6

Мой код:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class GFG {

    
    private static int MinAbsDifferences(List<Integer> arr)
    {

        Collections.sort(arr);

        int n = arr.size();


        int diff = 0;


        diff += Math.abs(arr.get(0) - arr.get(1));


        diff += Math.abs(arr.get(n - 1) - arr.get(n - 2));


        for (int i = 1; i < n - 1; i++)
            diff += Math.min(Math.abs(arr.get(i) - arr.get(i - 1)),
                            Math.abs(arr.get(i) - arr.get(i + 1)));


        return diff;
    }

  
    public static void main(String args[])
    {


        List<Integer> arr = new ArrayList<>();
        arr.add(5);
        arr.add(1);
        arr.add(3);
        arr.add(7);
        arr.add(3);

        System.out.println( "Diff = "
                + MinAbsDifferences(arr));
    }


}

Однако я считаю, что это не оптимально, хотя первоначальная система получила выговор

I/P : 2,3,2
O/P : 1

Однако , это привело к 2. Когда я запустил dry, я думаю, что все тестовые примеры с моей стороны были правильными, и приведенное выше должно привести к 1, не понимаю, почему они получили как 2.

Что может ошиблись там с моим кодом?

Answer 1

Есть разные способы сделать это. Вы можете попробовать один из них как:

int arr[] = {5,1,3,7,3}; 

// Sort array
Arrays.sort(arr);
        
int sum = 0;
// Find difference between adjacent elements
for(int i=0; i<arr.length-1; i++) {
    sum += arr[i+1] - arr[i];
}
System.out.println(sum);

Answer 2

Чтобы решить эту проблему, отсортируйте массив, а затем просуммируйте разницу между каждым элементом и предыдущим элементом, начиная со второго (с индексом, равным единице).

Вы можете использовать Streams для выполнения sh это. Демо

final int arr[] = {5,1,3,7,3};
Arrays.sort(arr);
final int sum = IntStream.range(1, arr.length).map(i->arr[i]-arr[i-1]).sum();
System.out.println(sum);//6

A for l oop также можно использовать. Демо

final int arr[] = {5,1,3,7,3};
Arrays.sort(arr);
int sum = 0;
for(int i = 1; i < arr.length; i++){
    sum += arr[i] - arr[i-1];
}
System.out.println(sum);//6