> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/merge-sort-realated/315.-count-of-smaller-numbers-after-self.md).

# 315. Count of Smaller Numbers After Self

![](/files/-MbFpV5BPs9VHUxw2uPa)

![](/files/-MbFpYXGP0m59MU4dmqG)

time: O(nlogn)

space: O(n)

這題認真去看可以發現, 其實主體就是 mergeSort, 但為什麼可以在 mergeSort 的過程中

達成 count 右邊比本身小的結果呢？

主要是要先利用一個 Item class, 來記錄原本的值和 index

還有利用一個 count 陣列, 來記錄最後的答案, 怎麼紀錄答案呢？

就是利用 Item class 裡面原本的值和 index

##

## 當第一個 while 時, 如果  

merge 5, 2

1\.

if (items\[l].val > items\[r].val)   => 

a. 代表目前是逆序(左邊 大於 右邊), 所以要 右邊 要移到 左邊, 才會是 sorted,  以這來說就是 item\[r++] 加到 temp

b. 但逆序也代表了一件事 =>  右邊有一個數大於左邊, 所以 rightCount++

else 也就是 sorted, 那要做什麼呢？ 就是要記錄結果到 count\[] 陣列, 因為已經沒有右邊比左邊大的 case 了

a. 記錄結果到 count\[] 陣列 .=> 這就要利用到 items\[l].idx 了 so count\[items\[l.idx]] += rightCount 

b. 把 l 目前內容加入, item\[l++] 加到 temp

ex 5, 2 .=> 2, 5 .,  rightCount++,  塞了 2 到  temp\[0]

![](/files/-MbG3WeX41XN8wvqVdCL)

```java
        while (l <= mid && r <= right) {
            if (items[l].val > items[r].val) { 
            // l > r, means move r to l, so insert r data to temp, 
            // and add rightcount , ex 5 2 => 2 5, but rightCount should++
                rightCount++;
                temp[tempIdx++] = items[r++];
            } else { 
            // if l < r, it is sorted, ex: 2 5, 
            // cal count result(count[l index] += rightCnt), 
            // insert l data to temp
                count[items[l].idx] += rightCount;
                temp[tempIdx++] = items[l++];
            }
   
        }
```

第二個 while 就跟 第一個 while else 其實內容一樣 （ 因為是 l <= mid)

```java
while (l <= mid) { // insert remained l data, and cal count, (insert l data means cal result!)
            count[items[l].idx] += rightCount;
            temp[tempIdx++] = items[l++];
        }
```

ex 5 2 .=> 2, 5 之後,  還剩下 5, 所以塞 5 到 temp\[1] .( while l <= mid

5 的 count+= rightCount, 也就是 count\[0] += 1&#x20;

### 接著是 merge 1,   and merge 2,5

![](/files/-MbG4_1ZzsKsyeRc6Vpi)

ex   2 .5  merge 1 時  =>&#x20;

lowPtr .           |    hiPtr&#x20;

2 .           5 .          1   &#x20;

\=> 經歷之前第一個 while 後  => 1 2 5 .=>  rightCount = 1

lowPtr .  mid         hiPtr&#x20;

2 .           5 .          1   &#x20;

while (l <= mid ) .=> 所以 2, 5 (count\[1],  count\[0])都要 += rightCount   (因為有個小的1 到左邊啦

![](/files/-MbG3ITL-eHQ-nz2waOm)

![](/files/-MbG3EElC_Dd3h41t2Xa)

```java
        while (l <= mid) { // insert remained l data, and cal count, (insert l data means cal result!)
            count[items[l].idx] += rightCount;
            temp[tempIdx++] = items[l++];
        }

        while (r <= right) { // insert remained r data
            temp[tempIdx++] = items[r++];
        }

        // finally put sorted temp data to items
        for (int p = 0; p < temp.length; p++) {
            items[left + p] = temp[p];
        }
```

&#x20;最後把 temp 結果(sort 的）, 更新到原本 items 中

```java
class Solution {
    private class Item { 
        int val;
        int idx;

        public Item(int val, int idx) {
            this.val = val;
            this.idx = idx; // for count use
        }
    }

    public List<Integer> countSmaller(int[] nums) {

        int n = nums.length;
        int[] count = new int[n];
        Item[] items = new Item[n];

        for (int i = 0; i < n; i++) {
            items[i] = new Item(nums[i], i);
        }

        mergeSort(items, 0, n - 1, count);

        List<Integer> result = new ArrayList<>();
        for (int cnt : count) {
            result.add(cnt);
        }

        return result;

    }

    private void mergeSort(Item[] items, int left, int right, int[] count) {

        if (left >= right) return;

        int mid = (right + left) >> 1;
        mergeSort(items, left, mid, count);
        mergeSort(items, mid + 1, right, count);
        merge(items, left, mid, right, count);

    }

    private void merge(Item[] items, int left, int mid, int right, int[] count) {

        Item[] temp = new Item[right - left + 1];
        int tempIdx = 0;

        int l = left;
        int r = mid + 1;
        int rightCount = 0;

        while (l <= mid && r <= right) {
            if (items[l].val > items[r].val) { 
            // l > r, means move r to l, so insert r data to temp, 
            // and add rightcount , ex 5 2 => 2 5, but rightCount should++
                rightCount++;
                temp[tempIdx++] = items[r++];
            } else { 
            // if l < r, it is sorted, ex: 2 5, 
            // cal count result(count[l index] += rightCnt), 
            // insert l data to temp
                count[items[l].idx] += rightCount;
                temp[tempIdx++] = items[l++];
            }
        }

        while (l <= mid) { // insert remained l data, and cal count, (insert l data means cal result!)
            count[items[l].idx] += rightCount;
            temp[tempIdx++] = items[l++];
        }

        while (r <= right) { // insert remained r data
            temp[tempIdx++] = items[r++];
        }

        // finally put sorted temp data to items
        for (int p = 0; p < temp.length; p++) {
            items[left + p] = temp[p];
        }
    }
}
```