315. calculate the number of elements on the right that are smaller than the current element

Preface

C++ It's a high-level programming language , from C Language expansion and upgrading , As early as 1979 By Benjani · Strauss LUP is AT&T Developed by Bell studio .
C++ Both can be carried out C Process programming of language , It can also be used for object-based programming characterized by abstract data types , It can also carry out object-oriented programming characterized by inheritance and polymorphism .C++ Good at object-oriented programming at the same time , You can also do process based programming .
C++ Have the practical characteristics of computer operation , At the same time, it is also committed to improving the programming quality of large-scale programs and the problem description ability of programming languages .

Java Is an object-oriented programming language , Not only absorbed C++ The advantages of language , It's abandoned C++ The incomprehensible inheritance in 、 Concepts such as pointer , therefore Java Language has two characteristics: powerful and easy to use .Java As the representative of static object-oriented programming language , Excellent implementation of object-oriented theory , Allow programmers to do complex programming in an elegant way of thinking .
Java It's simple 、 object-oriented 、 Distributed 、 Robustness, 、 Security 、 Platform independence and portability 、 Multithreading 、 Dynamic and so on .Java Can write desktop applications 、Web Applications 、 Distributed system and embedded system applications, etc .

Python By Guido of the Dutch Society for mathematical and computer science research · Van rosum On 1990 It was designed in the early 's , As a course called ABC A substitute for language .Python Provides efficient advanced data structure , It's also a simple and effective way of object-oriented programming .Python Syntax and dynamic types , And the nature of interpretative language , Make it a programming language for scripting and rapid application development on most platforms , With the continuous update of the version and the addition of new language features , Gradually used for independent 、 Development of large projects .
Python The interpreter is easy to extend , have access to C Language or C++（ Or something else can be done through C Calling language ） Expand new functions and data types .Python It can also be used as an extensible programming language in customizable software .Python Rich library of standards , Provides source code or machine code for each major system platform .
2021 year 10 month , Compiler for language popularity index Tiobe take Python Crowned the most popular programming language ,20 Put it in... For the first time in years Java、C and JavaScript above .

describe

Give you an array of integers nums , Returns a new array as required counts . Array counts It has this property ： counts[i] The value of is   nums[i] Right side less than nums[i] The number of elements .

Example 1：

Input ：nums = [5,2,6,1]
Output ：[2,1,1,0]
explain ：
5 On the right side of the wall is 2 A smaller element (2 and 1)
2 On the right side of the road is just 1 A smaller element (1)
6 On the right side of the wall is 1 A smaller element (1)
1 On the right side of the wall is 0 A smaller element

Example 2：

Input ：nums = [-1]
Output ：[0]

Example 3：

Input ：nums = [-1,-1]
Output ：[0,0]

class Solution {
    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;
    }
}