Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1348
Question Name: Inverse Pairs
Question Description: Given an integer array, for any two numbers, if the former one is less than the latter one, they are an inversion pair. Compute the total count of inversion pairs in the given array.
Input: the input might contain multiple test cases. Each test case contains two lines. The first line includes only one integer N (1 <= N <= 10^5), saying the number of elements in the test array. The second line includes N integers as the content of the array.
Output: for each test case, print out the number of inversion pairs.
1 2 3 4 5 | Input: 4 7 5 6 4 Output: 5 |
One same challenge as one from Codility. The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/05/2014 * Last updated: 09/05/2014 * * Filename: InversePairs.java * Compilation: javac InversePairs.java * Execution: java InversePairs * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * The utility to count the inverse pairs in an integer array. * @author Sheng Yu codesays.com */ public class InversePairs { /** * Count the inverse pairs in the given array. Do a merge sort, and count * the sum of swap distance. * @param input an array of integers * @return the number of inverse pairs in the input array. */ public long countInversePairs(int[] input) { int[] temp = new int[input.length]; int segLen = 1; long count = 0; // Do a bottom-up merge sort while (segLen < input.length) { for (int begin = 0; begin < input.length; begin += (segLen << 1)) { int firstBegin = begin; int firstEnd = begin + segLen; if (firstEnd >= input.length) break; int secondBegin = begin + segLen; int secondEnd = Math.min(secondBegin + segLen, input.length); int resultBegin = begin; // Merge sort these two sub-array to the temp array. int tempIndex = 0; while (firstBegin < firstEnd && secondBegin < secondEnd) { if (input[firstBegin] <= input[secondBegin]) { temp[tempIndex++] = input[firstBegin++]; } else { temp[tempIndex++] = input[secondBegin++]; count += firstEnd - firstBegin; } } while (firstBegin < firstEnd) { temp[tempIndex++] = input[firstBegin++]; } while (secondBegin < secondEnd) { temp[tempIndex++] = input[secondBegin++]; } // Write the temp array back to original positions for (int i = 0; i < tempIndex; ++i) { input[resultBegin + i] = temp[i]; } } segLen *= 2; } return count; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int[] unsorted = null; int inputSize = 0; InversePairs pairs = new InversePairs(); while (st.nextToken() != StreamTokenizer.TT_EOF) { inputSize = (int) st.nval; unsorted = new int[inputSize]; for (int i = 0; i < inputSize; ++i) { st.nextToken(); unsorted[i] = (int) st.nval; } System.out.println(pairs.countInversePairs(unsorted)); } } } |