Блог пользователя dash_______

Автор dash_______, 4 года назад, По-английски

INVERSION COUNT IN AN ARRAY

Given an array arr of size n we have to find the inversion count in the array.

what is inversion count :- sum of inversion count of all indexes.

inversion count of index i = number of index j such that j>i and arr[i]>arr[j]

or number of indexes with value lesser the arr[i] in the right of index i.

OR

number of index j such that j<i and arr[j]>arr[i] or number of indexes with value greater the arr[i] in the left of index i.


Example

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

for index 0 :- 0
for index 1 :- 3 ( index '2','3','4')
for index 2 :- 0
for index 3 :- 1 ( index '4')
for index 4 :- 0

so the inversion count of above array is equal to 0 + 3 + 0 + 1 + 0 = 4





BRUTE FORCE METHOD

Brute method use two loops.

  1. Outer loop traverse the whole array.

  2. Inner loop count the inversion count for particular index i.

CODE


int Inversion_Count(int arr[],int n){ int inversion_count=0; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(arr[i]>arr[j]){ inversion_count+=1; } } } }

TIME COMPLEXITY :- O(N^2) SPACE COMPLEXITY :- O(1)

USING MERGE SORT

basic merge sort algorithm


step 1 :- divide the array in two equal parts step 2 :- sort the two equal parts step 3 :- merge two sorted parts **for sorting two equal parts we again use merge sort**

more on merge sort

Now, how merge sort can be used to find inversion count.

while merging two sorted array

if left[i]<=right[j] continue

if left[i]>right[j] then this right[j] is smaller than all the next upcoming elements in left so, for every next element in left right[j] is smaller so inversion count should be increased by (size of left array)-i.

CODE


int inversion_count=0; int merge(int arr[],int l,int mid,int r){ int* temp = new int[r-l+1]; int i=l,j=mid+1; int t=0; while(i<=mid && j<=r){ if(arr[i]<=arr[j]){ temp[t++]=arr[i++]; } else{ temp[t++]=arr[j++]; inversion_count+=(mid-i+1); } } while(i<=mid){ temp[t++]=arr[i++]; } while(j<=r){ temp[t++]=arr[j++]; } t=0; for(int i=l;i<=r;i++){ arr[i]=temp[t++]; } delete [] temp; } int merge_sort(int arr[],int l,int r){ if(l>=r){ return 0; } int mid=(l+r)/2; merge_sort(arr,l,mid); //recursive calls to sort left part merge_sort(arr,mid+1,r); //recursive calls to sort right part merge(arr,l,mid,r); }

TIME COMPLEXITY :- O(NlogN) SPACE COMPLEXITY :- O(N)

USING BINARY INDEXED TREE/FENWICK TREE

for finding inversion count for index i in the given array. we can find number of index j such that j<i and arr[j]>arr[i]. BIT uses the fact that a number can be broken into several powers of 2.

In BIT index i stores the sum or product or anything of previous m elements of array. where
m is 2^LSB of i.

like this

BASIC BIT CODE

const int N=1e6;
int BIT[N];

// indexing in BST starts from 1

void add(int idx,int val){     // val is added to index a
    int i=idx;
    while(i<N){
        BIT[i]+=val;
        i+=(i&(-i));
    }
}

int query(int idx){           // returns sum of values from range 1 to idx
    int sum=0;
    while(idx>0){
        sum+=BIT[idx];
        idx+=(idx&(-idx));
    }
    return sum;
} 


more on BIT

we can take array elements as indexes for BIT array such that BIT array store count of value arr[i].

while traversing given array arr we keep on increasing count of arr[i] in the bit array and

calculating number of indexes with value greater than arr[i] or (i — number of index with

value less than equal to arr[i]).

number of index with value less than equal to arr[i] = query(arr[i]).

CODE

const int N=1e6;
int BIT[N];

// indexing in BST starts from 1

void add(int idx,int val){     // val is added to index a
    while(idx<N){
        BIT[idx]+=val;
        idx+=(idx&(-idx));
    }
}

int query(int idx){           // returns sum of values from range 1 to idx
    int sum=0;
    while(idx>0){
        sum+=BIT[idx];
        idx-=(idx&(-idx));
    }
    return sum;
} 


int inversion_count(int arr[],int n){
    int icount=0;
    for(int i=1;i<=n;i++){
        add(arr[i],1);         // increases the count of arr[i] by 1
        int a=query(arr[i]);   // a stores number of indexes with value less than and equal to arr[i]

        icount+=(i-a);
    }
    return icount;
}


TIME COMPLEXITY :- O(NlogN) SPACE COMPLEXITY :- O(N)

note :- since we used array elements as indexes so we cannot use this method if values in array are greater than 1e9 because we cannot create an array of such a bigger size in C++ and if array contains 0 as element then also we cannot use this method.

  • Проголосовать: нравится
  • -45
  • Проголосовать: не нравится