My simple AC Java Binary Search code


  • 76
    M

    Traverse from the back to the beginning of the array, maintain an sorted array of numbers have been visited. Use findIndex() to find the first element in the sorted array which is larger or equal to target number. For example, [5,2,3,6,1], when we reach 2, we have a sorted array[1,3,6], findIndex() returns 1, which is the index where 2 should be inserted and is also the number smaller than 2. Then we insert 2 into the sorted array to form [1,2,3,6].

    public List<Integer> countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        List<Integer> sorted = new ArrayList<Integer>();
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = findIndex(sorted, nums[i]);
            ans[i] = index;
            sorted.add(index, nums[i]);
        }
        return Arrays.asList(ans);
    }
    private int findIndex(List<Integer> sorted, int target) {
        if (sorted.size() == 0) return 0;
        int start = 0;
        int end = sorted.size() - 1;
        if (sorted.get(end) < target) return end + 1;
        if (sorted.get(start) >= target) return 0;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (sorted.get(mid) < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        if (sorted.get(start) >= target) return start;
        return end;
    }
    

    Due to the O(n) complexity of ArrayList insertion, the total runtime complexity is not very fast, but anyway it got AC for around 53ms.


  • 8
    Q

    java 12ms use the BST

    class TreeNode {
    int val;
    int num;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
    val = x;
    num = 0;
    }
    }

    public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        if(nums.length == 0)
            return new ArrayList<Integer>();
        List<Integer> list = new ArrayList<Integer>();
        List<Integer> list1 = new ArrayList<Integer>();
        TreeNode root = new TreeNode(nums[nums.length-1]);
        root.num=1;
        list.add(0);
        for(int i = nums.length-2;i >= 0;i--){
            list.add(get(root,nums[i],0));
        }
        for(int i = nums.length-1;i >= 0;i--)
            list1.add(list.get(i));
        return list1;
    }
    public int get(TreeNode root,int val,int num){
        if(root.val >= val){
            root.num = root.num+1;
            if(root.left == null)
            {
                TreeNode node = new TreeNode(val);
                node.num = 1;
                root.left = node;
                return num;
            }else{
                return get(root.left,val,num);
            }
        }else{
            num += root.num;
            if(root.right == null){
                TreeNode node = new TreeNode(val);
                node.num = 1;
                root.right = node;
                return num;
            }else{
                return get(root.right,val,num);
            }
        }
    }
    

    }


  • 0
    W

    Nice!```````````````


  • 1
    R

    What's the complexity of building that tree? Is that O(n^2) worst case?


  • 0
    B

    why not use Collections.reverse(list); return list;


  • 2
    B

    The worst time complexity is also O(n^2)?


  • 0
    I

    Thank you for sharing your code. Here is C++ version of yours.

    // returns the index right after the first smaller element
    int findIndex(int target, vector<int>& sorted)
    {
        if (sorted.size() == 0) return 0;
        if (sorted.front() >= target) return 0;
        int ret = 0;
        int start = 0;
        int end = sorted.size()-1;
        while (start <= end)
        {
            int mid = start + (end-start)/2;
            if (sorted[mid] < target) 
            {
                ret = mid; start = mid+1;
            } 
            else 
            {
                end = mid-1;
            }
        }
        return ret+1;
        
    }
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size() - 1;
        vector<int> sorted;
        vector<int> res(nums.size());
        for (int i = n; i >= 0; i--)
        {
            int idx = findIndex(nums[i], sorted);
            sorted.insert(sorted.begin()+idx, nums[i]);
            res[i] = idx;
        }
        return res;
    }

  • 0
    L

    Can you give a hint why at the end we have "if (sorted.get(start) >= target) return start;" ?


  • 1
    M

    Hi Longstation, it's a general binary search. Here our goal is to find the smallest index which has number >= target. After we go out of the loop, we will only have two indexes [start, end]. So if start satisfies the condition it must the answer(start is smaller than end), else it would be end.


  • 0
    L

    Hi mayanist, thank you for the timely help. I changed that part of your code slightly, so, basically, for the binary search part, instead of checking "start + 1 < end", we do "start < end". Thus at the end, we don't need to check "sorted.get(start) >= target". I just posted the modified code with a reference to your original code.
    https://leetcode.com/discuss/77547/simple-accepted-java-solution


  • 2

    In the worst case, it's O(n^2) time complexity.


  • 1
    J

    What is the worst case? Time complexity of binary search is always log(n), so together with the for loop, the time complexity should be O(NlogN).


  • 0
    L

    @jigsaw_Becky, not really, depends on the implementation of the sorted array, even if we use BST to maintain the sorted array, it is still amortized O(nlogn) because of the self-balancing mechanism. so this algorithm is O(n^2) in worst case.


  • 5
    M

    As I said, here the insertion operation of ArrayList is O(n), thus the worse case here would be O(n^2)


  • 0
    Y

    Very nice solution. A small suggestion about the binary search part. If you have (start < end), then start index will be the solution.

    while (start < end) {
        int mid = start + (end - start) / 2;
        if (sorted.get(mid) < target) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return start;

  • 0
    G

    I don't think this works for 1-element list


  • 0
    Y

    1 element case won't make it to the binary search part, if (sorted.get(end) < target) return end + 1; if (sorted.get(start) >= target) return 0; will return it


  • 0

    Easy to understand, nice!


  • 0

    A java code with some improvement in the process of binary search

    public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        Integer[] res = new Integer[nums.length];
        List<Integer> sortedlist = new ArrayList<Integer>();
        for(int i = nums.length-1 ; i >= 0 ; i--) {
            int index = findindex(sortedlist , nums[i]);
            res[i] = index;
            sortedlist.add(index , nums[i]);
        }
        return Arrays.asList(res);
    }
    
    protected int findindex(List<Integer> sortedlist , int target) {
        if(sortedlist.size() == 0) return 0;
        int start = 0;
        int end = sortedlist.size()-1;
        if(sortedlist.get(start) >= target) return 0;
        if(sortedlist.get(end) < target) return end+1;
        while(start <= end) {
            int mid = start + (end - start) / 2;
            if(sortedlist.get(mid) < target) {
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        return start; // which can make sure we will return the first index of the target(there may be several target in the list)
    }
    

    }


  • 0
    J

    good idea though


Log in to reply
 

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