[LeetCode][658. Find K Closest Elements] 4 Approaches: Two Pointers, Sorting, Priority Queue and Binary Search

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 5.2k 阅读时长 ≈ 5 分钟

By Long Luo

This article is the solution 4 Approaches: Two Pointers, Sorting, Priority Queue and Binary Search of Problem 658. Find K Closest Elements.

Here shows 4 Approaches to slove this problem: Two Pointers, Sorting, Priority Queue and Binary Search with Two Pointers.

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// TP time: O(n) space: O(1)
public static List<Integer> findClosestElements(int[] arr, int k, int x) {
    List<Integer> ans = new ArrayList<>();
    int len = arr.length;
    int targetPos = -1;
    int delta = Integer.MAX_VALUE;
    for (int i = 0; i < len; i++) {
        if (Math.abs(arr[i] - x) < delta) {
            delta = Math.abs(arr[i] - x);
            targetPos = i;
        }
    }

    ans.add(arr[targetPos]);
    k--;

    int left = targetPos - 1;
    int right = targetPos + 1;
    while (k > 0) {
        if (left >= 0 && right < len && Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) {
            ans.add(arr[left]);
            left--;
            k--;
        } else if (left >= 0 && right < len && Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
            ans.add(arr[right]);
            right++;
            k--;
        } else if (left >= 0 && right == len) {
            ans.add(arr[left]);
            left--;
            k--;
        } else if (left < 0 && right < len) {
            ans.add(arr[right]);
            right++;
            k--;
        }
    }

    Collections.sort(ans);

    return ans;
}

Analysis

  • Time Complexity: \(O(n + k \log k)\).
  • Space Complexity: \(O(n)\).

Sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// Sort time: O(nlogn) space: O(logn)
public static List<Integer> findClosestElements_sort(int[] arr, int k, int x) {
    List<Integer> list = new ArrayList<>();
    for (int e : arr) {
        list.add(e);
    }

    Collections.sort(list, new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            if (Math.abs(a - x) != Math.abs(b - x)) {
                return Math.abs(a - x) - Math.abs(b - x);
            }

            return a - b;
        }
    });

    List<Integer> ans = list.subList(0, k);
    Collections.sort(ans);
    return ans;
}

Analysis

  • Time Complexity: \(O(n \log n + k \log k)\).
  • Space Complexity: \(O(n)\).

Priority Queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<Integer> findClosestElements(int[] arr, int k, int x) {
    List<Integer> ans = new ArrayList<>();

    PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            if (Math.abs(a - x) == Math.abs(b - x)) {
                return a - b;
            }
            return Math.abs(a - x) - Math.abs(b - x);
        }
    });

    for (int num : arr) {
        pq.offer(num);
    }

    while (!pq.isEmpty() && ans.size() < k) {
        ans.add(pq.poll());
    }

    Collections.sort(ans);

    return ans;
}

Analysis

  • Time Complexity: \(O(n \log n + k \log k)\)
  • Space Complexity: \(O(n)\)

BinarySearch

Since the array is sorted, so it’s easy to use the Binary Search method to find the closest element of \(\textit{x}\), then we start to find the other closest elements both the left and right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// BinarySearch time: O(n) space: O(1)
public static List<Integer> findClosestElements_bs(int[] arr, int k, int x) {
    List<Integer> ans = new ArrayList<>();
    int len = arr.length;
    int targetPos = binarySearch(arr, x);
    ans.add(arr[targetPos]);
    k--;

    int left = targetPos - 1;
    int right = targetPos + 1;
    while (k > 0) {
        if (left >= 0 && right < len && Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) {
            ans.add(arr[left]);
            left--;
            k--;
        } else if (left >= 0 && right < len && Math.abs(arr[left] - x) > Math.abs(arr[right] - x)) {
            ans.add(arr[right]);
            right++;
            k--;
        } else if (left >= 0 && right == len) {
            ans.add(arr[left]);
            left--;
            k--;
        } else if (left < 0 && right < len) {
            ans.add(arr[right]);
            right++;
            k--;
        }
    }

    Collections.sort(ans);

    return ans;
}

private static int binarySearch(int[] arr, int target) {
    int len = arr.length;
    if (arr[0] >= target) {
        return 0;
    } else if (arr[len - 1] <= target) {
        return len - 1;
    }

    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (arr[mid] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    if (Math.abs(arr[left] - target) <= Math.abs(arr[left + 1] - target)) {
        return left;
    } else {
        return left + 1;
    }
}

The code is too obscure, we can just find the closest element which gt than \(\textit{x}\), then use two pointers to search other \(\textit{k}\) elements from both sides.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// BinarySearch Opt time: O(logn+k) space: O(1)
public static List<Integer> findClosestElements_bs_opt(int[] arr, int k, int x) {
    int len = arr.length;
    int right = binarySearchRight(arr, x);
    int left = right - 1;
    while (k-- > 0) {
        if (left < 0) {
            right++;
        } else if (right >= len) {
            left--;
        } else if (Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) {
            left--;
        } else {
            right++;
        }
    }

    List<Integer> ans = new ArrayList<>();
    for (int i = left + 1; i < right; i++) {
        ans.add(arr[i]);
    }

    return ans;
}

private static int binarySearchRight(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

Analysis

  • Time Complexity: \(O(\log n + k)\).
  • Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗