Why can my simply Java code accepted with running time 102ms?


  • 3
    L
    private void add(int[] bit, int i, int val) {
        for (; i < bit.length; i += 1) bit[i] += val;
    }
    
    private int query(int[] bit, int i) {
        return bit[i];
    }
    
    public List<Integer> countSmaller(int[] nums) {
        int[] tmp = nums.clone();
        Arrays.sort(tmp);
        for (int i = 0; i < nums.length; i++) {
        	nums[i] = Arrays.binarySearch(tmp, nums[i]);
        }
        int[] bit = new int[nums.length];
        Integer[] ans = new Integer[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            ans[i] = query(bit, nums[i]);
            add(bit, nums[i]+1, 1);
        }
        return Arrays.asList(ans);
    }

  • 0
    V

    damn smart accumulation solution!Though it is N^2, it looks so cool.


  • 0
    C

    because the average complexity is 0(N^2)


  • 0
    K
    This post is deleted!

Log in to reply
 

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