Guest User

Untitled

a guest
Sep 20th, 2021
63
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class Solution {
  2.  
  3. public long countInversions(int[] arr) {
  4.  
  5. return mergeSort(arr, 0, arr.length - 1);
  6.  
  7. }
  8.  
  9.  
  10.  
  11. private long mergeSort(int[] arr, int start, int end) {
  12.  
  13. if (start >= end) {
  14.  
  15. return 0;
  16.  
  17. }
  18.  
  19. int mid = start + (end - start) / 2;
  20.  
  21. int count = 0;
  22.  
  23. count += mergeSort(arr, start, mid);
  24.  
  25. count += mergeSort(arr, mid + 1, end);
  26.  
  27. count += merge(arr, start, mid, end);
  28.  
  29. return count;
  30.  
  31. }
  32.  
  33.  
  34.  
  35. private long merge(int[] arr, int start, int mid, int end) {
  36.  
  37. int left = start;
  38.  
  39. int right = mid + 1;
  40.  
  41. int[] tmp = new int[end - start + 1];
  42.  
  43. int k = 0;
  44.  
  45. int count = 0;
  46.  
  47. while (left<= mid && right<= end) {
  48.  
  49. if (arr[left] > arr[right]) {
  50.  
  51. // count inversions between left & right array
  52.  
  53. count += end - right + 1;
  54.  
  55. tmp[k++] = arr[left++];
  56.  
  57. } else {
  58.  
  59. tmp[k++] = arr[right++];
  60.  
  61. }
  62.  
  63. }
  64.  
  65.  
  66.  
  67. while (left<= mid) {
  68.  
  69. tmp[k++] = arr[left++];
  70.  
  71. }
  72.  
  73.  
  74.  
  75. while (right<= end) {
  76.  
  77. tmp[k++] = arr[right++];
  78.  
  79. }
  80.  
  81. // copy tmp to array, can replace
  82.  
  83. // by System.arraycopy method
  84.  
  85. for (int i = 0; i<tmp.length; i++) {
  86.  
  87. arr[i + start] = tmp[i];
  88.  
  89. }
  90.  
  91. return count;
  92.  
  93. }
  94.  
  95. }
RAW Paste Data