315. Count of Smaller Numbers After Self.md

315. Count of Smaller Numbers After Self

---

leetcode-cn Daily Challenge on July 11th, 2020.

---

Difficulty : Hard

Related Topics : Binary Search、Binary Indexed Tree、Divide and Conquer、Sort、Segment Tree

---

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.

---

Solution

• mine
  • Java
    • BinarySearch Runtime: 15 ms, faster than 44.86%, Memory Usage: 41.5 MB, less than 62.16% of Java online submissions

      // O(N*logN)time
      // O(N^2)space
      public List<Integer> countSmaller(int[] nums) {
          if(nums == null){
              return new LinkedList<>();
          }
          List<Integer> res = new LinkedList<>();
          List<Integer> record = new ArrayList<>();
          for(int i = nums.length - 1; i >= 0; i--){
              int index = findIndex(record, nums[i]);
              res.add(0, index);
              record.add(index, nums[i]);
          }
          return res;
      }
      
      int findIndex(List<Integer> list, int value){
          int s = 0, e = list.size();
          while(s < e){
              int mid = (s + e) >> 1;
              if(list.get(mid) < value){
                  s = mid + 1;
              }else{
                  e = mid;
              }
          }
          return s;
      }
      

---

• the most votes
  • Segment Tree Runtime: 11 ms, faster than 53.80%, Memory Usage: 41.5 MB, less than 69.71% of Java online submissions

    // O(N*logN)time
    // O(N)space
    private int[] c;
    private int[] a;
    
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> resultList = new ArrayList<Integer>(); 
        discretization(nums);
        init(nums.length + 5);
        for (int i = nums.length - 1; i >= 0; --i) {
            int id = getId(nums[i]);
            resultList.add(query(id - 1));
            update(id);
        }
        Collections.reverse(resultList);
        return resultList;
    }
    
    private void init(int length) {
        c = new int[length];
        Arrays.fill(c, 0);
    }
    
    private int lowBit(int x) {
        return x & (-x);
    }
    
    private void update(int pos) {
        while (pos < c.length) {
            c[pos] += 1;
            pos += lowBit(pos);
        }
    }
    
    private int query(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret += c[pos];
            pos -= lowBit(pos);
        }
    
        return ret;
    }
    
    private void discretization(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        int size = set.size();
        a = new int[size];
        int index = 0;
        for (int num : set) {
            a[index++] = num;
        }
        Arrays.sort(a);
    }
    
    private int getId(int x) {
        return Arrays.binarySearch(a, x) + 1;
    }
    

---

• FenwickTree(Binary Indexed Tree)
  • Runtime: 26 ms, faster than 27.81%, Memory Usage: 42.3 MB, less than 24.32% of Java online submissions

    // O(N*logN)time
    // O(N)space
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int[] t = new int[set.size()];
        int index = 0;
        for (int num : set) {
            t[index++] = num;
        }
        Arrays.sort(t);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < index; i++) {
            map.put(t[i], i + 1);
        }
        FenwickTree tree = new FenwickTree(index);
        for (int i = len - 1; i >= 0; i--) {
            res.add(0, tree.query(map.get(nums[i]) - 1));
            tree.update(map.get(nums[i]), 1);
        }
        return res;
    }
    
    class FenwickTree{
        int[] tree;
        int size;
    
        public FenwickTree(int size){
            this.size = size;
            tree = new int[size + 1];
        }
    
        int lowBit(int x){
            return x & -x;
        }
    
        public void update(int i, int add){
            while(i <= size){
                tree[i] += add;
                i += lowBit(i);
            }
        }
    
        public int query(int i){
            int res = 0;
            while(i > 0){
                res += tree[i];
                i -= lowBit(i);
            }
            return res;
        }
    }
    

---