通过指令创建有序数组

题目

题目来源：力扣（LeetCode）

给你一个整数数组 instructions ，你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums ，你需要 从左到右 遍历 instructions 中的元素，将它们依次插入 nums 数组中。每一次插入操作的 代价 是以下两者的 较小值 ：

nums 中 严格小于 instructions[i] 的数字数目。
nums 中 严格大于 instructions[i] 的数字数目。
比方说，如果要将 3 插入到 nums = [1,2,3,5] ，那么插入操作的 代价 为 min(2, 1) (元素 1 和 2 小于 3 ，元素 5 大于 3 ），插入后 nums 变成 [1,2,3,3,5] 。

请你返回将 instructions 中所有元素依次插入 nums 后的 总最小代价 。由于答案会很大，请将它对 109 + 7 取余 后返回。

示例 1：

输入：instructions = [1,5,6,2]
输出：1
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 5 ，代价为 min(1, 0) = 0 ，现在 nums = [1,5] 。
插入 6 ，代价为 min(2, 0) = 0 ，现在 nums = [1,5,6] 。
插入 2 ，代价为 min(1, 2) = 1 ，现在 nums = [1,2,5,6] 。
总代价为 0 + 0 + 0 + 1 = 1 。

示例 2:

输入：instructions = [1,2,3,6,5,4]
输出：3
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 2 ，代价为 min(1, 0) = 0 ，现在 nums = [1,2] 。
插入 3 ，代价为 min(2, 0) = 0 ，现在 nums = [1,2,3] 。
插入 6 ，代价为 min(3, 0) = 0 ，现在 nums = [1,2,3,6] 。
插入 5 ，代价为 min(3, 1) = 1 ，现在 nums = [1,2,3,5,6] 。
插入 4 ，代价为 min(3, 2) = 2 ，现在 nums = [1,2,3,4,5,6] 。
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。

示例 3：

输入：instructions = [1,3,3,3,2,4,2,1,2]
输出：4
解释：一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3,3] 。
插入 2 ，代价为 min(1, 3) = 1 ，现在 nums = [1,2,3,3,3] 。
插入 4 ，代价为 min(5, 0) = 0 ，现在 nums = [1,2,3,3,3,4] 。
插入 2 ，代价为 min(1, 4) = 1 ，现在 nums = [1,2,2,3,3,3,4] 。
插入 1 ，代价为 min(0, 6) = 0 ，现在 nums = [1,1,2,2,3,3,3,4] 。
插入 2 ，代价为 min(2, 4) = 2 ，现在 nums = [1,1,2,2,2,3,3,3,4] 。
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。

思路分析

1. 线段树区间查询⽤循环实现;
2. 对于每⼀个要插⼊的数x，只查询⼤于x的数。⼩于x的数⽤总数减出来。

/**
 * @param {number[]} instructions
 * @return {number}
 */
var Tree = function (maxNum) {
  var treeSize = maxNum & (maxNum - 1) == 0 ? 2 * maxNum : 4 * maxNum;
  this.treeArr = new Array(treeSize).fill(0);
};
Tree.prototype.getRangeCount = function (targetStart, targetEnd, currStart, currEnd, n = 0) {
  if (targetEnd < currStart || targetStart > currEnd) {
    return 0;
  }
  if (targetStart <= currStart && targetEnd >= currEnd) {
    return this.treeArr[n];
  }
  // 开始二分
  var temp = (currStart + currEnd) >> 1;
  var a = this.getRangeCount(targetStart, targetEnd, currStart, temp, n * 2 + 1);
  var b = this.getRangeCount(targetStart, targetEnd, temp + 1, currEnd, n * 2 + 2);
  return a + b;
}
Tree.prototype.addNum = function (num, currStart, currEnd, n = 0) {
  if (currStart <= num && currEnd >= num) {
    this.treeArr[n]++;
    if (currStart != currEnd) {
      // 二分赋值
      var temp = (currStart + currEnd) >> 1;
      this.addNum(num, currStart, temp, n * 2 + 1);
      this.addNum(num, temp + 1, currEnd, n * 2 + 2);
    }
  }
}
var createSortedArray = function (instructions) {
  // 直接使用搜索树无法获取相对数量!
  // 使用线段树统计!
  size = instructions.length;
  if (size < 3) {
    return 0;
  }
  var maxNum = Number.MIN_VALUE;
  for (i = 0; i < size; i++) {
    maxNum = Math.max(instructions[i], maxNum);
  }
  var tree = new Tree(maxNum);
  tree.addNum(instructions[0], 0, maxNum)
  tree.addNum(instructions[1], 0, maxNum)
  var ret = 0;
  var pivot = 1000000007;
  for (i = 2; i < size; i++) {
    // 比新插入值小的数字的数量
    var temp1 = tree.getRangeCount(0, instructions[i] - 1, 0, maxNum);
    temp1 = Math.min(temp1, i - temp1);
    // 比新插入值大的数字的数量
    var temp2 = tree.getRangeCount(instructions[i] + 1, maxNum, 0, maxNum);
    temp2 = Math.min(temp2, i - temp2);
    var cost = Math.min(temp1, temp2);
    ret += cost;
    ret = ret % pivot;
    tree.addNum(instructions[i], 0, maxNum);
  }
  return ret;
};