Leetcode - Count of Smaller Numb

My code:

import java.util.Arrays;
import java.util.List;

public class Solution {
    class Node {
        int val = 0;
        int sum = 0;
        int dup = 0;
        Node left;
        Node right;
        Node(int val, int sum) {
            this.val = val;
            this.sum = sum;
            this.dup = 1;
        }
    }
    
    
    public List<Integer> countSmaller(int[] nums) {
        Node root = null;
        Integer[] arr = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            root = helper(root, nums[i], i, arr, 0);
        }
        
        return Arrays.asList(arr);
    }
    
    private Node helper(Node root, int num, int i, Integer[] arr, int preSum) {
        if (root == null) {
            root = new Node(num, 0);
            arr[i] = preSum;
        }
        else if (root.val == num) {
            root.dup++;
            arr[i] = preSum + root.sum;
        }
        else if (root.val < num) {
            root.right = helper(root.right, num, i, arr, preSum + root.sum + root.dup);
        }
        else {
            root.sum += 1;
            root.left = helper(root.left, num, i, arr, preSum);
        }
        return root;
    }
    
}

reference:
https://discuss.leetcode.com/topic/31405/9ms-short-java-bst-solution-get-answer-when-building-bst/2

这道题目的这个解法，还是很难理解的。花了挺长一段时间去理解。
做难题真的花时间，今天的效率也真够低的。
他通过建立一个 类似于BST的树，来解决这个问题。
sum 存的是，当前结点所表示的value，和当前访问处的value，这段范围内，小于当前结点value的个数。
比较绕。
preSum 表示的是，当前结点表示的value，在该value右侧，比他小的个数

比如：
[3, 2, 1, 2, 6, 1]
1(0, 1) sum = 0, dup = 1
=>
1(0, 1)
\ preSum = 0 + 0 + 1
6(0, 1)

=>
1(0, 1)
\ preSum = 0 + 0 + 1
6(1, 1) dup++
/ preSum = 1
2(0, 1)

=>
1(0, 2) dup++

6(1, 1)
/
2(0, 1)

=>

1(0, 2)

6(1, 1)
/
2(0, 2) dup++
preSum = preSum + root.sum

=>

1(0, 2)

6(1, 1)
/
2(0, 2)

3(0, 1)

还是不太好理解的。

Solution2:
My code:

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        Integer[] ret = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = findIndex(list, nums[i]);
            ret[i] = index;
            list.add(index, nums[i]);
        }
        
        return Arrays.asList(ret);
    }
    
    private int findIndex(List<Integer> ret, int target) {
        if (ret.size() == 0) {
            return 0;
        }
        int begin = 0;
        int end = ret.size() - 1;
        
        while (begin <= end) {
            int mid = begin + (end - begin) / 2;
            if (ret.get(mid) > target) {
                end = mid - 1;
            }
            else if (ret.get(mid) < target) {
                begin = mid + 1;
            }
            else {
                while (mid - 1 >= 0 && ret.get(mid - 1).equals(ret.get(mid))) {
                    mid--;
                }
                return mid;
            }
        }
        return begin;
    }
}

reference:
https://discuss.leetcode.com/topic/31173/my-simple-ac-java-binary-search-code/2

这个时间复杂度很大。
注意， Integer 比较，用 .equals() !!!!!

还有一种 Merge sort的写法，以后再理解吧。

Anyway, Good luck, Richardo! -- 10/08/2016

My code:

public class Solution {
    int[] count;
    int[] index;
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> ret = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return ret;
        }
        
        int len = nums.length;
        count = new int[len];
        index = new int[len];
        for (int i = 0; i < len; i++) {
            index[i] = i;
        }
        
        mergesort(nums, 0, len - 1);
        
        for (int i = 0; i < count.length; i++) {
            ret.add(count[i]);
        }
        
        return ret;
    }
    
    private void mergesort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergesort(nums, start, mid);
        mergesort(nums, mid + 1, end);
        merge(nums, start, mid, end);
    }
    
    private void merge(int[] nums, int start, int mid, int end) {
        int[] arr = new int[end - start + 1];
        for (int i = start; i <= end; i++) {
            arr[i - start] = nums[i];
        }
        int[] temp = new int[end - start + 1];
        for (int i = start; i <= end; i++) {
            temp[i - start] = index[i];
        }
        
        int p = start;
        int p1 = start;
        int p2 = mid + 1;
        int cnt = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1 - start] > arr[p2 - start]) {
                cnt++;
                index[p] = temp[p2 - start];
                nums[p] = arr[p2 - start];
                p++;
                p2++;
            }
            else {
                index[p] = temp[p1 - start];
                nums[p] = arr[p1- start];
                count[index[p]] += cnt;
                p++;
                p1++;
            }
        }
        
        while (p2 <= end) {
            index[p] = temp[p2 - start];
            nums[p] = arr[p2 - start];
            p++;
            p2++;
        }
        
        while (p1 <= mid) {
            index[p] = temp[p1 - start];
            nums[p] = arr[p1 - start];
            count[index[p]] += cnt;
            p++;
            p1++;
        }
    }
}

这是一种新的办法，并且可以保证时间复杂度是 O(nlogn)
上面的BST方法，在最坏情况下复杂度是 O(n^2)

这个 merge sort 方法其实挺难理解的。问了同学才略懂。
当我们merge 到一层时，假设有左右两个部分，left and right
left is sorted and right is sorted
然后我们 merge 的时候，
right部分的所有元素， 他们的 count of smaller numbers 一定是 0!
我们要关注的是左部分。 left part
如果 left[p1] < right[p2]
按照以往的merge sort经验，我们有一个arrray来放merge过后的新数组。

nums[p] = left[p1]
p++;
p1++;

if left[p1] > right[p2]
nums[p] = right[p2];
p++;
p2++;

这里要注意了，我们需要记录的，是右侧比左侧小的个数。
所以我们有一个变量 cnt
当 left[p1] > right[p2]
我们需要把right[p2] 移动到 left[p1] 的左侧，记住，这个时候，
对于 left[p1, mid],他们的 count of smaller numbers 至少有了1，即,这个 right[p2]
同时，因为merge sort, 原有的顺序都被打乱了。我们需要记录下，新merge过的数组，他们的元素，在原数组中的index
这样，当我们发现右边比左边小时，cnt++
当我们发现左边比右边小时，就可以更新 count 了
对应的index 就是 index[p]

差不多理解下把。

Anyway, Good luck, Richardo! -- 10/09/2016