Binary search (or insert sort) solution


  • 0
    X

    The idea is, inserting integers one by one into an array from back to front of nums. Each insertion will not change the ascending order of that array by using binary search. After insertion finishes, the index of the position for the insertion would give the number of smaller integers for a element in nums. It is because we start from back, so in each insertion, elements in that ordered array would be elements after the element that we are doing insertion in nums, and then binary search the ordered array gives how many elements are smaller than current element, which are also after current element in nums.

    class Solution {
       public List<Integer> countSmaller(int[] nums) {
            ArrayList<Integer> container = new ArrayList<>();
            List<Integer> ret = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                ret.add(0);
            }
    
            for (int i = nums.length - 1; i >= 0; i--) {
                ret.set(i, findCount(container, i, nums));
            }
            return ret;
        }
    
        public int findCount(ArrayList<Integer> container, int index, int[] nums) {
            int i = 0, j = container.size() - 1;
            int target = nums[index];
            while (i <= j) {
                int mid = i + (j - i) / 2;
                if (container.get(mid) >= target) {
                    j = mid - 1;
                } else {
                    i = mid + 1;
                }
            }
    
            container.add(i, target);
            return i;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.