Find the number of inversions in an array
Page 1 of 1
Find the number of inversions in an array
inversion means for i< j, a[i] > a[j], in other words, they are the parts that are not well sorted. For example, in array {1, 5, 7, 9, 10, 6, 20}, the number of inversions is 3: {7, 6}, {9, 6}, {10, 6}
1____long long reversal_num(int* a, int num) {
2__________if (num<=1) return 0;
3__________int nl = num/2;
4__________int nr = num-nl;
5__________long long left_inv = reversal_num(a, nl);
6__________long long right_inv = reversal_num(a+nl, nr);
7____
8__________int* left = new int[nl+1];
9__________int* right = new int[nr+1];
10_________for (int i=0; i<nl; i++) left[i] = a[i];
11_________for (int i=nl; i<num; i++) right[i-nl] = a[i];
12_________left[nl] = numeric_limits<int>::max();
13_________right[nr] = left[nl];
14___
15_________int i = 0;
16_________int j = 0;
17_________long long inv_num = left_inv+right_inv;
18___
19_________for (int p=0; p<num; p++)
20_______________if (left[i] <= right[j]) a[p] = left[i++];
21_______________else {
22_____________________a[p] = right[j++];
23_____________________inv_num += nl-i;
24_______________}
25___
26_________delete[] left;
27_________delete[] right;
28_________return inv_num;
29___}
1____long long reversal_num(int* a, int num) {
2__________if (num<=1) return 0;
3__________int nl = num/2;
4__________int nr = num-nl;
5__________long long left_inv = reversal_num(a, nl);
6__________long long right_inv = reversal_num(a+nl, nr);
7____
8__________int* left = new int[nl+1];
9__________int* right = new int[nr+1];
10_________for (int i=0; i<nl; i++) left[i] = a[i];
11_________for (int i=nl; i<num; i++) right[i-nl] = a[i];
12_________left[nl] = numeric_limits<int>::max();
13_________right[nr] = left[nl];
14___
15_________int i = 0;
16_________int j = 0;
17_________long long inv_num = left_inv+right_inv;
18___
19_________for (int p=0; p<num; p++)
20_______________if (left[i] <= right[j]) a[p] = left[i++];
21_______________else {
22_____________________a[p] = right[j++];
23_____________________inv_num += nl-i;
24_______________}
25___
26_________delete[] left;
27_________delete[] right;
28_________return inv_num;
29___}
viterbi- Posts : 32
Join date : 2011-09-03
Similar topics
» An array of integers, all appear twice except one, find this number.
» In an array there is one element which repeats more than n/2 times...find the number in 0(n) time and 0(1) space
» Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).
» Given a magic number sum, to find if there are two numbers whose sum equals to the number
» print all subsets of an array whose sum equals one number
» In an array there is one element which repeats more than n/2 times...find the number in 0(n) time and 0(1) space
» Given a sorted array find all possible |ai - aj| where ai,aj belongs to Array A. n^2 is obvious. Find a solution in O(N).
» Given a magic number sum, to find if there are two numbers whose sum equals to the number
» print all subsets of an array whose sum equals one number
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|