剑指 Offer 51. 数组中的逆序对

粗糙的代码，返回值都还不匹配：

  1. var reversePairs = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 1) {
  4.         return 0;
  5.     }
  7.     let mid = Math.floor(n / 2);
  8.     let lowArray = reversePairs(nums.slice(0, mid));
  9.     let highArray = reversePairs(nums.slice(mid));
  11.     let tmp = [];
  12.     let i = 0;
  13.     let j = 0;
  15.     let count = 0;
  16.     for (let x = 0; x < n; x++) {
  17.         if (i === mid) {
  18.             j++;
  19.             continue;
  20.         }
  21.         if (j === (n - mid)) {
  22.             i++;
  23.             continue;
  24.         }
  25.         if (lowArray[i] < highArray[j]) {
  26.             count++;
  27.             i++;
  28.         } else {
  29.             j++;
  30.         }
  31.     }
  33.     return count;
  34. };

reversePairs 希望返回的是个数，归并排序中的两个有序数组，可以考虑合并到一个数组(一般叫这个数组为帮助数组，这里起名 tmp)里返回，而且 tmp 可以做到全局唯一。之前总是隐隐戳戳地觉得可能下标关系对不上，其实不用操心，对于分治思想，操作的总是自己的区间，不会影响他人的。

写了一个上午，终于写完，磕磕巴巴的，得总结总结：

  1. var reversePairs = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 1) {
  4.         return 0;
  5.     }
  7.     let count = 0;
  8.     let tmp = new Array(n);
  10.     function sort(left, right) { // 不穿数组，传下标
  11.         if (left === right) {
  12.             tmp[left] = nums[left];
  13.             return;
  14.         }
  16.         let mid = left + Math.floor((right - left) / 2);
  17.         sort(left, mid);
  18.         sort(mid + 1, right);
  20.         merge(left, mid, right);
  21.     }
  23.     function merge(left, mid, right) {
  24.         let i = left; // 左
  25.         let j = mid + 1;
  26.         let arr = new Array(); // 这个结构能省吗？
  28.         for (let x = left; x <= right; x++) {
  29.             if (i === mid + 1) {
  30.                 arr[x] = tmp[j];
  31.                 j++;
  32.                 continue;
  33.             }
  34.             if (j === right + 1) {
  35.                 arr[x] = tmp[i];
  36.                 i++;
  37.                 continue;
  38.             }
  39.             if (tmp[i] > tmp[j]) {
  40.                 arr[x] = tmp[j];
  41.                 count += mid - i + 1;
  42.                 j++;
  43.             } else {
  44.                 arr[x] = tmp[i];
  45.                 i++;
  46.             }
  47.         }
  49.         for (let y = left; y <= right; y++) {
  50.             tmp[y] = arr[y];
  51.         }
  52.     }
  54.     sort(0, n - 1);
  56.     return count;
  57. };

找到了我这种写法的弊病了，正确写法：（思想在注释里）

  1.     function merge(left, mid, right) {
  2.         // 1. 从 nums[left...right] 复制 到 tmp[left, right]
  3.         for (let x = left; x <= right; x++) {
  4.             tmp[x] = nums[x];
  5.         }
  7.         // 2. tmp[left, mid] 和 tmp[mid + 1, right] 归并排序覆盖到 nums[left...right] 里
  8.         // 我之前不放心的一点是，tmp 里面的顺序怎么办，其实 在递归的第一步都是从 nums 里拿数据，tmp 就真是 暂时的
  9.         let i = left; // 左
  10.         let j = mid + 1;
  11.         // let arr = new Array(); // 这个结构能省吗？
  13.         for (let x = left; x <= right; x++) {
  14.             if (i === mid + 1) {
  15.                 nums[x] = tmp[j];
  16.                 j++;
  17.                 continue;
  18.             }
  19.             if (j === right + 1) {
  20.                 nums[x] = tmp[i];
  21.                 i++;
  22.                 continue;
  23.             }
  24.             if (tmp[i] > tmp[j]) { // 出现逆序对
  25.                 nums[x] = tmp[j];
  26.                 count += mid - i + 1;
  27.                 j++;
  28.             } else {
  29.                 nums[x] = tmp[i];
  30.                 i++;
  31.             }
  32.         }
  33.     }

很神奇的是，提升非常的大！
image.png

image.png

315. 计算右侧小于当前元素的个数

  1. var countSmaller = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 1) {
  4.         return [0];
  5.     }
  7.     let result = new Array(n).fill(0);
  8.     let indexArray = new Array(n).fill().map((value, index) => index); // 引入索引数组
  9.     let tmp = new Array(n);
  11.     function sort(left, right) { // 不穿数组，传下标
  12.         if (left === right) {
  13.             return;
  14.         }
  16.         let mid = left + Math.floor((right - left) / 2);
  17.         sort(left, mid);
  18.         sort(mid + 1, right);
  20.         merge(left, mid, right);
  21.     }
  23.     function merge(left, mid, right) {
  24.         // 1. 从 nums[left...right] 复制 到 tmp[left, right]
  25.         for (let x = left; x <= right; x++) {
  26.             // tmp[x] = nums[x];
  27.             tmp[x] = indexArray[x]; // 改为索引数组
  28.         }
  30.         let i = left; // 左
  31.         let j = mid + 1;
  33.         for (let x = left; x <= right; x++) {
  34.             if (i === mid + 1) {
  35.                 indexArray[x] = tmp[j];
  36.                 j++;
  37.                 continue;
  38.             }
  39.             if (j === right + 1) {
  40.                 indexArray[x] = tmp[i];
  41.                 result[tmp[i]] += right - mid; // 这里要新增
  42.                 i++;
  43.                 continue;
  44.             }
  46.             if (nums[tmp[i]] <= nums[tmp[j]]) { // 需要归并的对象是 tmp 里的元素，明白这一点！！nums[]只是比较规则而已
  47.                 // indexArray[i] = j;
  48.                 // indexArray[tmp[i]] = tmp[j];
  49.                 indexArray[x] = tmp[i]; // 是这个
  50.                 result[tmp[i]] += j - mid - 1;
  51.                 i++;
  52.             } else {
  53.                 indexArray[x] = tmp[j];
  54.                 j++;
  55.             }
  56.         }
  57.     }
  59.     sort(0, n - 1);
  61.     return result;
  62. };

对比 51 和 351 的写法，非常的像：
image.png

493. 翻转对

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var reversePairs = function(nums) {
  6.     let n = nums.length;
  7.     if (n <= 1) {
  8.         return 0;
  9.     }
  11.     let count = 0;
  12.     let tmp = new Array(n);
  14.     sort(0, n - 1); // 左右都闭，容易处理
  16.     function sort(left, right) {
  17.         if (left === right) {
  18.             return;
  19.         }
  21.         let mid = left + Math.floor((right - left) / 2);
  22.         sort(left, mid);
  23.         sort(mid + 1, right);
  25.         merge(left, mid, right); // [left...mid] 和 [mid+1...right] 都有序
  27.         function merge(left, mid, right) {
  28.             for (let x = left; x <= right; x++) {
  29.                 tmp[x] = nums[x];
  30.             }
  32.             let i = left;
  33.             let j = mid + 1;
  35.             for (let k = left; k <= right; k++) {
  36.                 if (i === mid + 1) {
  37.                     nums[k] = tmp[j];
  38.                     j++;
  39.                     continue;
  40.                 }
  41.                 if (j === right + 1) {
  42.                     nums[k] = tmp[i];
  43.                     i++;
  44.                     continue;
  45.                 }
  47.                 if (tmp[i] <= tmp[j]) {
  48.                     nums[k] = tmp[i];
  49.                     i++;
  50.                 } else {
  51.                     nums[k] = tmp[j];
  52.                     j++;
  53.                 }
  54.             }
  57.             // 上面是正常的归并排序
  58.             // 下面，tmp[i] > 2 * tmp[j] 这个比较会影响正常的排序，所以单独拿出出来
  59.             i = left;
  60.             j = mid + 1;
  62.             for (let k = left; k <= right; k++) {
  63.                 if (i === mid + 1) {
  64.                     j++;
  65.                     continue;
  66.                 }
  67.                 if (j === right + 1) {
  68.                     i++;
  69.                     continue;
  70.                 }
  71.                 if (tmp[i] > 2 * tmp[j]) {
  72.                     count += mid - i + 1;
  73.                     j++;
  74.                 } else {
  75.                     i++;
  76.                 }
  77.             }
  79.         }
  81.     }
  83.     return count;
  84. };

327. 区间和的个数

朴素的暴力解，一点都不好看。

  1. var countRangeSum = function(nums, lower, upper) {
  2.     let n = nums.length;
  4.     let count = 0;
  5.     let sum;
  6.     for (let i = 0; i < n; i++) {
  7.         sum = 0;
  8.         for (let j = i; j <= n; j++) {
  9.             sum += nums[j];
  10.             if (lower <= sum && sum <= upper) {
  11.                 count++;
  12.             }
  13.         }
  14.     }
  16.     return count;
  17. }

这道题，看不出半点 需要归并排序的地方啊：
看不懂：
https://leetcode-cn.com/problems/count-of-range-sum/solution/qu-jian-he-de-ge-shu-by-leetcode-solution/
前缀和：
image.png