BiruLyu
7/25/2017 - 2:56 AM

## 315. Count of Smaller Numbers After Self(#MergeSort).java

``````public class Solution {

if(nums.length==0)return res;
TreeNode root = new TreeNode(nums[nums.length-1]);
for(int i=nums.length-2;i>=0;i--){
}
return res;
}
private int insert(TreeNode t, int v){
if(t.val==v){
t.repeat++;
return t.smaller;
}
else{
int sum=0;
while(true){
if(t.val>v){
t.smaller++;
if(t.left == null){
t.left = new TreeNode(v);
break;
}
else{
t=t.left;
}
}
else if(t.val<v){
if(t.right == null){
t.right = new TreeNode(v);
sum += (t.smaller+t.repeat);
break;
}
else{
sum += (t.smaller+t.repeat);
t = t.right;
}
}
else{
t.repeat += 1;
sum += t.smaller;
break;
}
}
return sum;
}
}
class TreeNode{
TreeNode left,right;
int repeat=1,smaller=0,val;
public TreeNode(int val){
this.val = val;
}
}
}``````
``````public class Solution {
public List<Integer> countSmaller(int[] nums) {
if(nums.length==0)return res;
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for(int i:nums)min = min>i ? i:min;
int[] nums2 = new int[nums.length];
for(int i=0;i<nums.length;i++){
nums2[i] = nums[i]-min;
max = max<nums2[i] ? nums2[i] : max;
}
int[] tree = new int[max+1];
for(int i=nums2.length-1;i>=0;i--){
update(nums2[i]+1,tree);
}
return res;
}
private int get(int index, int[] tree){
int sum=0;
while(index>0){
sum += tree[index];
index -= (index&(~index+1));
}
return sum;
}
private void update(int index,int[] tree){
while(index < tree.length){
tree[index]++;
index += (index&(~index+1));
}
}
}``````
``````
public class Solution {
class NumWithIndex {
int val;
int idx;
int cnt;

NumWithIndex (int val, int idx) {
this.val = val;
this.idx = idx;
this.cnt = 0;
}
}
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length < 1) return res;
int len = nums.length;
NumWithIndex[] numsIdx = new NumWithIndex[len];
for (int i = 0; i < len; i++) {
numsIdx[i] = new NumWithIndex(nums[i], i);
}
NumWithIndex[] helper = new NumWithIndex[len];
mergeSort(numsIdx, helper, 0, len - 1);
int[] temp = new int[len];
for (NumWithIndex num : numsIdx) {
temp[num.idx] = num.cnt;
}
for (int cnt : temp) {
}
return res;
}

private void mergeSort(NumWithIndex[] nums, NumWithIndex[] helper, int start, int end) {
if (end <= start) return;
int mid = start + (end - start) / 2;
mergeSort(nums, helper, start, mid);
mergeSort(nums, helper, mid + 1, end);

mergeAndCount(nums, helper, start, end);
}

private void mergeAndCount(NumWithIndex[] nums, NumWithIndex[] helper, int start, int end) {
int mid = start + (end - start) / 2;
int i = start;
int j = mid + 1;
int count = 0;
while (i <= mid) {
if (j <= end && nums[i].val > nums[j].val) {
count++;
j++;
} else {
nums[i].cnt += count;
i++;
}
}

// merge
for (i = start; i <= end; i++) {
helper[i] = nums[i];
}
i = start;
j = mid + 1;
int k = start;
while (i <= mid && j <= end) {
if (helper[i].val <= helper[j].val) {
nums[k++] = helper[i++];
} else {
nums[k++] = helper[j++];
}
}
while (i <= mid) {
nums[k++] = helper[i++];
}
}
}``````