Java code using Binary Search, similar to #35. Search Insert Position


  • 0
    J

    This problem could be solved using the same method as in #35. Search Insert Position.

    We traverse the array from the end to the beginning and keep adding the number to a sorted list that contains the numbers we already see. For each number we see, use binary search to find its position in the sorted list, and such index would be the count of numbers smaller that required. Add the number to the list at the position and keep going to the next one.

    class Solution {
        public List<Integer> countSmaller(int[] nums) {
            
            List<Integer> list = new ArrayList<Integer>();
            if(nums == null || nums.length == 0) return list;
            
            Integer[] res = new Integer[nums.length];
            List<Integer> sorted = new ArrayList<Integer>();
    
            for(int i = nums.length - 1; i >= 0; i --) {
                res[i] = findIdx(sorted, nums[i]);
                sorted.add(res[i], nums[i]);
            }
            list = Arrays.asList(res);
            return list;
        }
    
        private int findIdx(List<Integer> sorted, int num) {
            if(sorted.size() == 0) return 0;
            int low = 0, high = sorted.size() - 1;
            while(low <= high) {
                int mid = low + (high - low)/2;
                if(sorted.get(mid) < num) low = mid + 1;
                else high = mid - 1;
            }
            return low;
        }
    }
    

Log in to reply
 

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