쌍의 절대 차이의 최소 합

문제 설명

길이 N이 같은 두 개의 배열 A와 B가 주어집니다. 작업은 배열 A의 각 요소를 배열 B의 요소와 연결하여 모든 쌍의 절대 차의 합이 최소가 되도록 하는 것입니다.

문제 설명에 대한 링크는 여기https://practice.geeksforgeeks.org/problems/minimum-sum-of-absolute-differences-of-pairs/1에서 찾을 수 있습니다.

샘플 입력 및 출력

Example 1

Input:
N = 4
A = {4,1,8,7}
B = {2,3,6,5}
Output:
6
Explanation:

If we take the pairings as (1,2), (4,3),(7,5), and (8,6), 
the sum will be 
S = |1 - 2| + |4 - 3| + |7 - 5| + |8 - 6|
  = 6
It can be shown that this is the minimum sum we can get.

예상 시간 복잡도: O(N*log(N))

예상 보조 공간: O(1)

해결책

이제 이 문제를 해결하는 방법은 문제 설명을 면밀히 살펴보면 절대 차이가 가능한 한 최소여야 함을 분명히 의미합니다.
유도 방법을 적용해 보겠습니다. 이제 2개의 배열을 고려하십시오.

X = [a, d, b, c]
Y = [c, d, b, a]

배열 X의 요소 a에 대해 Y에 가장 가까운 숫자가 있어야 할 때 최소값이 옵니다. 따라서 배열 X 내의 'b'는 배열 Y로 매핑되어야 합니다. 완료되면 이 배열은 다음과 같습니다.

X = [a, b, c, d]
Y = [a, b, c, d]
Difference = 0

여기서 결론은 두 어레이에서 동일한 순서를 가져야 한다는 것입니다. 즉, 배열을 오름차순 또는 내림차순으로 정렬해야 합니다.

여기에서는 기본 자연 정렬 순서, 즉 오름차순을 선택했습니다. 이 접근 방식을 통해 우리는 아래 솔루션을 제시합니다.

class Solution { 
    long findMinSum(int[] a,int[] b, int n) { 
        if(a.length != b.length) 
            throw new IllegalArgumentException();
        long res = 0l;
        Arrays.sort(a);
        Arrays.sort(b);
        for(int i = 0; i < a.length; i++) {
            res += Math.abs(a[i] - b[i]);
        }
        return res;
    }
}