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

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)

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.

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

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

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

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