Task description A zero-indexed array A consisting of N integers is given. An inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P]. Write a function: class Solution { public int solution(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. // you can also use imports, for example: // import java.util.*; // you can...
Comments
Post a Comment