AC Java Solution with PriorityQueue, the O(log n) Time Complexity?


  • 0
    X
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<Integer>();
        Queue<Double> q = new PriorityQueue<>(new Comparator<Double>(){
        @Override
            public int compare(Double arg0, Double arg1)
        {
                if (arg1 < arg0)
                {
                    return -1;
                }
                if ( arg1  > arg0 )
                {
                    return 1;
                }
                return 0;
        }
    });
    HashMap<Double,ArrayList<Integer>> hm = new  HashMap<Double,ArrayList<Integer>>();
    dfs(q, root, target, k,hm);
    for(ArrayList<Integer> list:hm.values()){
        res.addAll(list);
    }
    return res;
    }
    public void dfs(Queue<Double> q, TreeNode root, double target, int k, HashMap<Double,ArrayList<Integer>> hm){
        if(root==null) return;
        q.offer(Math.abs(root.val-target));
        if(!hm.containsKey(Math.abs(root.val-target))){
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(root.val);
            hm.put(Math.abs(root.val-target),tmp);
        }
        else{
            hm.get(Math.abs(root.val-target)).add(root.val);
        }
        if(q.size()>k){
            hm.get(q.peek()).remove(0);
            if(hm.get(q.peek())==null) hm.remove(q.peek());
            q.poll();
        }
        dfs(q,root.left,target,k,hm);
        dfs(q,root.right,target,k,hm);
    }

  • 0
    H

    Similar idea here, but I used an inner class instead.
    I am just afraid, by using the priorityQueue, we did not use the property of BST at all.

    private class MyNode{
        int val;
        //TreeNode node;
        private MyNode(int val){
            this.val = val;
           // this.node = node;
        }
    }
    
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        PriorityQueue<MyNode> pq = new PriorityQueue<MyNode>(new Comparator<MyNode>(){
            public int compare(MyNode node1, MyNode node2){
                if(Math.abs(target - node1.val) < Math.abs(target - node2.val)){
                    return -1;
                }else if(Math.abs(target - node1.val) == Math.abs(target - node2.val)){
                    return 0;
                }else{
                    return 1;
                }
            }
        });
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        //TreeNode curr = root;
        stack.push(root);
        
        while(!stack.isEmpty()){
            TreeNode curr = stack.pop();
            pq.offer(new MyNode(curr.val));
            
            if(curr.left != null) stack.push(curr.left);
            if(curr.right != null) stack.push(curr.right);
        }
        
        List<Integer> result = new ArrayList<Integer>();
        
        for(int i = 0; i < k; i++){
            result.add(pq.poll().val);
        }
        
        return result;
    }

  • 0
    B

    this is not o(logn) time. this is o(n) time.


Log in to reply
 

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