ArrayInversionCount

1. ArrayInversionCount

Compute number of inversion in an array.

Task description

A zero-indexed array A consisting of N integers is given. An inversionis a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].

Write a function:

int solution(vector<int> &A);

that computes the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.

Assume that:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

For example, in the following array:

A[0] = -1 A[1] = 6 A[2] = 3
A[3] =  4 A[4] = 7 A[5] = 4

there are four inversions:

  (1,2)  (1,3)  (1,5)  (4,5)

so the function should return 4.

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 2009–2014 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

접근방법 두가지

1. 1) A를 Merge_Sort한 B를 생성

    2) A의 앞부터 하나씩 꺼내면서 B에서 위치를 찾음. 찾은 위치 Index값이 Inversion 개수.

        A와 B에서 방금 원소를 삭제함

    3) A가 비어버릴때까지 2)를 반복하며 Inversion개수를 더한 결과가 정답

2. 1) A를 Merge_Sort하는 각 Step에서 Merge시 Right원소가 Left원소보다 작은게 나올때마다 Inversion개수 증가

    2) Merge_Sort가 종료되는 시점에서 1)단계의 각 Inversion개수의 합이 정답.

* 퀵소트는 최악의 경우 O(n^2)의 수행 시간이 소모 되므로 머지 소트를 사용함.

#include <string.h> typedef std::vector<int>::iterator vec_it; int merge(vector<int> left_vec, vector<int> right_vec, vec_it numbers) { vec_it left = left_vec.begin(); vec_it left_end = left_vec.end(); vec_it right = right_vec.begin(); vec_it right_end = right_vec.end(); int count = 0; int left_index = 0; int left_size = left_vec.size(); while ( left < left_end && right < right_end ) { if ( *left <= *right ) { *numbers = *left; ++left; ++left_index; } else { *numbers = *right; ++right; count += left_size - left_index; } ++numbers; } while (left < left_end) { *numbers = *left; ++numbers; ++left; } while (right < right_end) { *numbers = *right; ++numbers; ++right; } return count; } int MergeSort ( vector<int> &B ) { if (B.size() <= 1) { return 0; } std::vector<int>::size_type middle = (B.size()) / 2; std::vector<int> left(B.begin(), B.begin() + middle); std::vector<int> right(B.begin() + middle, B.end()); return MergeSort(left) + MergeSort(right) + merge(left, right, B.begin()); } int solution(vector<int> &A) { // write your code in C++11 return MergeSort ( A ); }