315. Count of Smaller Numbers After Self

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]

        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)

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

接著是 merge 1, and merge 2,5

ex 2 .5 merge 1 時 =>

lowPtr . | hiPtr

2 . 5 . 1

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

lowPtr . mid hiPtr

2 . 5 . 1

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

        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];
        }

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

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];
        }
    }
}