Very Concise Binary Search Solution 9line


  • 1
    S
    public int reversePairs(int[] nums) {
    	int n = nums.length, res = 0;
    	if (n <2) return res;
    	List<Long> list = new ArrayList<>();
    	list.add(2*(long)nums[n-1]);
    	for (int j = n-2; j >= 0; j--) {
    		res += bs((long)nums[j], list);
    		list.add(bs(2*(long)nums[j], list), 2*(long)nums[j]);
    	}
    	return res;
    }
    	
    // binary search
    private int bs (long val, List<Long> list) {
    	int l = 0, r = list.size()-1;
    	while (l<=r) {
    		int m = (l+r)/2;
    		if (list.get(m) < val) l = m+1;
    		else r = m-1;
    	}
    	return l;
    }
    

  • 1
    I

    it's O(n^2) time complexity for the moving of elements in List, the code will get TLE sometimes.


  • 0
    S

    @immortalCockroach oh, you're right, most time pass, but sometimes TLE, Thank for your reminder.


Log in to reply
 

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