Striver의 SDE 시트 여정 - #12 배열의 역전 계산

Problem Statement :-

솔루션 1

1. run another loop from j=i+1 to n.

check, if arr[i] > arr[j] is true, then increase the inversion count.

3단계 끝.

자바

public class Solution {
    public static long getInversions(long arr[], int n) {
        long pairs =0;

     for(int i=0; i<arr.length;i++){

          for(int j=i+1; j<arr.length;j++){

              if(arr[i] > arr[j]) pairs++;
          }
      }
      return pairs;
    }
}

솔루션 2

병합 정렬 알고리즘을 사용하여 이 문제를 해결할 수도 있습니다. 병합 정렬 알고리즘에서 두 개의 정렬된 하위 배열을 병합하는 방법을 알고 있다면 이 솔루션을 쉽게 이해할 수 있습니다.

하위 배열을 병합하는 동안 반전 쌍을 계산하고,
왼쪽 부분배열의 요소가 오른쪽 부분배열의 요소보다 큰 경우.

두 개의 하위 배열을 병합하면서 이 문제를 해결하는 방법을 시각적으로 이해합시다.
Array = [5,3,2,1,4]


보시다시피 5는 3보다 큽니다. 즉, 반전 쌍의 첫 번째 조건을 충족하고 두 번째 조건인 i<j도 충족합니다.
두 개의 하위 배열을 병합하는 동안 첫 번째 반전 쌍을 찾았습니다.
쌍 - (5,3)
3 > 2 & 5 > 2 이 쌍도 두 조건을 모두 만족하면 반전 쌍으로 계산합니다.
쌍 - (3,2) (5,2)

이번에는 왼쪽 부분배열 요소1가 오른쪽 부분배열 요소4보다 크지 않아 반전 쌍의 첫 번째 조건을 충족하지 않습니다.

2 > 1 그러면 - (2,1) (3,1) (5,1) 쌍을 만들 수 있습니다.2 < 4 조건을 만족하지 않습니다.3 < 4 조건을 만족하지 않습니다.5 > 4 그럼 - (5,4)

자바

public class Solution {
    public static long getInversions(long arr[], int n) {
        // Write your code here.
        long[] ans = new long[1];
        mergeSort(arr,0,arr.length-1,ans);

      return ans[0];
    }

    private static void mergeSort(long[] arr,int left,int right,long[] ans){

    // return if arr size becomes 1
    if(left >= right) return;


    // calculate the mid
    int mid = ( left + right ) / 2;


    mergeSort(arr,left,mid,ans);
    mergeSort(arr,mid+1,right,ans);

    merge(arr,left,mid,right,ans);

   }

     private static void merge(long[] arr,int left,int mid,int right,long[] ans){

    // calculate the size of left & right subarrays
    int leftArrSize = mid - left+1;
    int rightArrSize = right - mid;

    // initialise temp subarrays
    long[] leftArr = new long[leftArrSize];
    long[] rightArr = new long[rightArrSize];

    // copy left & right array into temp arrays
    for (int i = 0; i < leftArrSize; ++i)
      leftArr[i] = arr[left + i];
    for (int j = 0; j < rightArrSize; ++j)
    rightArr[j] = arr[mid + 1 + j];

    // set initial indexes of subarrays
    int leftPointer = 0;
    int rightPointer = 0;
    int arrPointer = left;

    // copy temp subarrays, in ascending order
    while(leftPointer < leftArrSize && rightPointer < rightArrSize ){

      if(leftArr[leftPointer] <= rightArr[rightPointer]){
        arr[arrPointer] = leftArr[leftPointer];
        arrPointer++;
        leftPointer++;
      }else{
        arr[arrPointer] = rightArr[rightPointer];
        arrPointer++;
        rightPointer++;
         ans[0] += leftArrSize - leftPointer; 
      }
    }


    // copy the remaining elements of left subarray into a marge array
    while(leftPointer < leftArrSize){
      arr[arrPointer] = leftArr[leftPointer];
      arrPointer++;
      leftPointer++;
    }

    // copy the remaining elements of right subarray into a merge array
    while(rightPointer < rightArrSize){
      arr[arrPointer] = rightArr[rightPointer];
      arrPointer++;
      rightPointer++;
    }



   }

}

시간 및 공간 복잡도는 병합 정렬 알고리즘, O(Nlogn), bcoz와 같을 것입니다. 반전 쌍을 계산하기 위한 몇 줄의 코드를 추가합니다.


이 기사를 읽어 주셔서 감사합니다. 오류를 발견하면 댓글 섹션에 알려주고 나중에 사용할 수 있도록 저장해 두십시오.