java 解法, 执行用时: 51 ms, 内存消耗: 61.7 MB, 提交时间: 2022-08-31 10:12:19

class Solution {
  private int[] index;
  private int[] helper;
  private int[] count;

  public List<Integer> countSmaller(int[] nums) {
    List<Integer> res = new ArrayList<>(nums.length);

    index = new int[nums.length];
    helper = new int[nums.length];
    count = new int[nums.length];
    for (int i = 0; i < index.length; i++) {
      index[i] = i;
    }

    merge(nums, 0, nums.length - 1);

    for (int i = 0; i < count.length; i++) {
      res.add(i, count[i]);
    }
    return res;
  }

  private void merge(int[] nums, int s, int e) {
    if (s == e || s > e) return;
    int mid = (s + e) >> 1;

    if (s < mid) {
      merge(nums, s, mid);
    }

    if (mid + 1 < e) {
      merge(nums, mid + 1, e);
    }

    int i = s, j = mid + 1;
    int hi = s;
    while (i <= mid && j <= e) {
      if (nums[index[i]] <= nums[index[j]]) {
        // 右侧出
        helper[hi++] = index[j++];
      } else {
        // 左侧出 计数
        count[index[i]] += e - j + 1;
        helper[hi++] = index[i++];
      }
    }

    while (i <= mid) {
      //左侧出
      helper[hi++] = index[i++];
    }

    while (j <= e) {
      // 右侧出
      helper[hi++] = index[j++];
    }

    for (int k = s; k <= e; k++) {
      index[k] = helper[k];
    }
  }
}

golang 解法, 执行用时: 216 ms, 内存消耗: 11.7 MB, 提交时间: 2022-08-31 10:11:04

// 离散化树状数组
var a, c []int

func countSmaller(nums []int) []int {
    resultList := []int{}
    discretization(nums)
    c = make([]int, len(nums) + 5)
    for i := len(nums) - 1; i >= 0; i-- {
        id := getId(nums[i])
        resultList = append(resultList, query(id - 1))
        update(id)
    }
    for i := 0; i < len(resultList)/2; i++ {
        resultList[i], resultList[len(resultList)-1-i] = resultList[len(resultList)-1-i], resultList[i]
    }
    return resultList
}

func lowBit(x int) int {
    return x & (-x)
}

func update(pos int) {
    for pos < len(c) {
        c[pos]++
        pos += lowBit(pos)
    }
}

func query(pos int) int {
    ret := 0
    for pos > 0 {
        ret += c[pos]
        pos -= lowBit(pos)
    }
    return ret
}

func discretization(nums []int) {
    set := map[int]struct{}{}
    for _, num := range nums {
        set[num] = struct{}{} 
    }
    a = make([]int, 0, len(nums))
    for num := range set {
        a = append(a, num)
    }
    sort.Ints(a)
}

func getId(x int) int {
    return sort.SearchInts(a, x) + 1
}