# 315.Count-of-Smaller-Numbers-After-Self

## 315. Count of Smaller Numbers After Self

## 题目地址

<https://leetcode.com/problems/count-of-smaller-numbers-after-self/>

## 题目描述

```
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:
Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
```

## 代码

### Approach #0 Binary Indexed Tree

```java
class Solution {
  class FenwickTree {
    private int[] sums;
    public FenwickTree(int n) {
      sums = new int[n + 1];
    }

    public void update(int i, int delta) {
      while (i < sums.length) {
        sums[i] += delta;
        i += lowbit(i);
      }
    }

    public int query(int i) {
      int sum = 0;
      while (i > 0) {
        sum += sums[i];
        i -= lowbit(i);
      }
      return sum;
    }

    private int lowbit(int x) {
        return x & -x;
      }
  };

  public List<Integer> countSmaller(int[] nums) {
    int[] sorted = Arrays.copyOf(nums, nums.length);
    Arrays.sort(sorted);
    Map<Integer, Integer> ranks = new HashMap();
    int rank = 0;
    for (int i = 0; i < sorted.length; i++) {
      if (i == 0 || sorted[i] != sorted[i - 1]) {
        ranks.put(sorted[i], ++rank);
      }
    }

    FenwickTree tree = new FenwickTree(ranks.size());
    List<Integer> ans = new ArrayList<Integer>();
    for (int i = nums.length - 1; i >= 0; i--) {
      int sum = tree.query(ranks.get(nums[i]) - 1);
      ans.add(sum);
      tree.update(ranks.get(nums[i]), 1);
    }

    Collections.reverse(ans);
    return ans;
  }  
}
```

### Approach #1 BST

Every node will maintain a val **sum** recording the total of number on it's left bottom side, **dup** counts the duplication. For example, \[3, 2, 2, 6, 1], from back to beginning,we would have:

```
                             1(0, 1)
                     \
                     6(3, 1)
                     /
                 2(0, 2)
                       \
                        3(0, 1)
```

```java
class Solution {
  class Node {
    Node left, right;
    int val, sum, dup = 1;
    public Node(int v, int s) {
      val = v;
      sum = s;
    }
  }

  public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
    Node root = null;
    for (int i = nums.length - 1; i >= 0; i--) {
      root = insert(nums[i], root, ans, i, 0);
    }
    return Arrays.asList(ans);
  }

  private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
    if (node == null) {
      node = new Node(num, 0);
      ans[i] = preSum;
    } else if (node.val == num) {
      node.dup++;
      ans[i] = preSum + node.sum;
    } else if (num < node.val) { // left
      node.sum++;
      node.left = insert(num, node.left, ans, i, preSum);
    } else { // right
      // num > node.val
      node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
    }

    return node;
  }
}
```

### Approach #2 Merge Sort

The smaller numbers on the right of a number are exactly those that jump from its right to its left during a stable sort. So I do mergesort with added tracking of those right-to-left jumps.

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

      int[] indexes = new int[nums.length];
      for (int i = 0; i < nums.length; i++) {
        indexes[i] = i;
      }
      mergesort(nums, indexes, 0, nums.length - 1, count);

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

  private void mergesort(int[] nums, int[] indexes, int start, int end, int[] count){
    if (end <= start)  return;

    int mid = (start + end) / 2;
    mergesort(nums, indexes, start, mid, count);
    mergesort(nums, indexes, mid + 1, end, count);

    merge(nums, indexes, start, end, count);
  }

  private void merge(int[] nums, int[] indexes, int start, int end, int[] count) {
    int mid = (start + end) / 2;
    int left_index = start;
    int right_index = mid + 1;
    int rightcount = 0;        
    int[] new_indexes = new int[end - start + 1];

    int sort_index = 0;
    while (left_index <= mid && right_index <= end) {
      if (nums[indexes[right_index]] < nums[indexes[left_index]]) {
        new_indexes[sort_index] = indexes[right_index];
        rightcount++;
        right_index++;
      } else {
        new_indexes[sort_index] = indexes[left_index];
        count[indexes[left_index]] += rightcount;
        left_index++;
      }
      sort_index++;
    }

    while (left_index <= mid){
      new_indexes[sort_index] = indexes[left_index];
      count[indexes[left_index]] += rightcount;
      left_index++;
      sort_index++;
    }

    while (right_index <= end){
      new_indexes[sort_index] = indexes[right_index];
      right_index++;
      sort_index++;
    }

    for (int i = start; i <= end; i++){
      indexes[i] = new_indexes[i - start]; // ？
    }
  }
}
```

### Approach #3 Merge Sort

```java
class Solution {
  public List<Integer> countSmaller(int[] nums) {
    int[] res = new int[nums.length];
    int[] index = new int[nums.length];
    for (int i = 0; i < res.length; i++) {
        index[i] = i;
    }
    mergeSort(nums, index, 0, nums.length - 1, res);
    List<Integer> list = new LinkedList<>();
    for (int i: res) {
        list.add(i);
    }
    return list;
  }

  private void mergeSort(int[] nums, int[] index, int l, int r, int[] res) {
    if (l >= r) {
        return;
    }
    int mid = (l + r) / 2;
    mergeSort(nums, index, l, mid, res);
    mergeSort(nums, index, mid + 1, r, res);
    merge(nums, index, l, mid, mid + 1, r, res);
  }

  private void merge(int[] nums, int[] index, int l1, int r1, int l2, int r2, int[] res) {
    int start = l1;
    int[] tmp = new int[r2 - l1 + 1];
    int count = 0;
    int p = 0;
    while (l1 <= r1 || l2 <= r2) {
      if (l1 > r1) {
        tmp[p++] = index[l2++];
      } else if (l2 > r2) {
        res[index[l1]] += count;
        tmp[p++] = index[l1++];
      } else if (nums[index[l1]] > nums[index[l2]]) {
        tmp[p++] = index[l2++];
        count++;
      } else {
        res[index[l1]] += count;
        tmp[p++] = index[l1++];
      }
    }
    for (int i = 0; i < tmp.length; i++) {
      index[start+i] = tmp[i];
    }
  }
}
```

### Approach #4 Segment tree

```cpp
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        if (nums == null || nums.length == 0) return new ArrayList<>();
        int[] minMax = getMinMax(nums);
        SegmentTreeNode root = new SegmentTreeNode(minMax[0], minMax[1]);
        LinkedList<Integer> ans = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            //query
            ans.addFirst(query(root, nums[i]));
            //update tree;
            update(root, nums[i]);
        }
        return ans;
    }
    private int query(SegmentTreeNode root, int num) {
        if (root == null || root.start >= num) return 0;
        if (num > root.end) return root.count;
        return query(root.left, num) + query(root.right, num);
    }
    private void update(SegmentTreeNode root, int num) {

        if (num < root.start || num > root.end) return;
        root.count++;
        if (root.start == root.end) return;
        int mid = root.start + (root.end - root.start) / 2;
        if (num <= mid) {
            if (root.left == null) { 
                root.left = new SegmentTreeNode(root.start, mid);
            }
            update(root.left, num);
        } else {
            if (root.right == null) {
                root.right = new SegmentTreeNode(mid + 1, root.end);
            }
            update(root.right, num);
        }
    }

    private int[] getMinMax(int[] nums) {
        int min = nums[0], max = nums[0];
        for (int n : nums) {
            min = min > n ? n : min;
            max = max < n ? n : max;
        }
        return new int[]{min, max};
    }
}
class SegmentTreeNode {
    int start;
    int end;
    int count;
    SegmentTreeNode left;
    SegmentTreeNode right;
    public SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
        this.count = 0;
    }
}
```

### Approach #5 binary search

```java
public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int[] res = new int[nums.length];
        List<Integer> list = new ArrayList<>();
        for(int i = nums.length - 1; i >= 0; i--) {
            res[i] = insert(list, nums[i]);
        }
        list.clear();
        for(int i = 0 ; i < nums.length; i++) {
            list.add(res[i]);
        }
        return list;
    }

    // binary insert
    private int insert(List<Integer> list, int num) {
        int l = 0;
        int r = list.size() - 1;
        while(l <= r) {
            int mid = l + (r - l)/2;
            int M = list.get(mid);
            if(M >= num) {
                r = mid - 1;
            }else if(M < num) {
                l = mid + 1;
            }
        }
        list.add(l, num);
        return l;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/bit/315.count-of-smaller-numbers-after-self.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.