O(n) Java Solution


  • 1
    W

    I have to say that it takes me several days to figure out this solution;
    My thought is actually pretty simple, suppose I get the whole sorted values, n elements, how can I get the k closest values?
    In order to get the sorted values, an inorder visit will work, which takes O(n) time;
    the next step is to get the K closest values; first thing is the find the most closest value; which is actually pretty easy, by comparing abs one by one, stoping at the index which increase the difference; it also takes O(n) time; second, we can use two pointers, i and j, at two ends of the range; step each pointer by comparing the abs difference at the next position;
    sorry for my poor English; I guess the code is more clear to understand;

    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> values = new ArrayList<>();
        visit(root, values);
    
        return helper(target, k, values);
    }
    
    public List<Integer> helper(double target, int k, List<Integer> values) {
        int x = 0;
        double minDiff = abs(target, values.get(x));
    
        for (x = 1; x < values.size(); x++) {
            double diff = abs(target, values.get(x));
            if (diff > minDiff) {
                break;
            }
            minDiff = diff;
        }
    
        x = x - 1;
    
        int i = x, j = x;
    
        while (j - i + 1 < k) {
            double diffOne = Double.MAX_VALUE;
            if (i > 0) {
                diffOne = abs(target, values.get(i - 1));
            }
            double diffTwo = Double.MAX_VALUE;
            if (j < values.size() - 1) {
                diffTwo = abs(target, values.get(j + 1));
            }
    
            if (diffOne < diffTwo) {
                i -= 1;
            } else {
                j += 1;
            }
        }
    
    
        return values.subList(i, j + 1);
    }
    
    private double abs(double a, int b) {
        return Math.abs(a - b);
    }
    
    private void visit(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
    
        visit(root.left, list);
        list.add(root.val);
        visit(root.right, list);
    }

Log in to reply
 

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