Java | slide window | binary search | 5 solutions
Slide Window + Binary Search\n\n\n    //Runtime: 3 ms, faster than 99.87% of Java online submissions for Find K Closest Elements.\n    //Memory Usage: 44.2 MB, 
# Slide Window + Binary Search\n\n```\n    //Runtime: 3 ms, faster than 99.87% of Java online submissions for Find K Closest Elements.\n    //Memory Usage: 44.2 MB, less than 93.40% of Java online submissions for Find K Closest Elements.\n    //Slide Window + Binary Search\n    //Time: O( lg(N-K) + K); Space: O(1)\n    public List<Integer> findClosestElements(int[] arr, int k, int x) {\n        int left = 0, right = arr.length - k;\n\n\t\t//find the left point\n        while (left < right) {\n            int mid = (left + right) / 2;\n            if (x - arr[mid] > arr[mid + k] - x)\n                left = mid + 1;\n            else right = mid;\n        }\n\n        List<Integer> res = new LinkedList<>();\n        right = left + k;\n        while (left < right) res.add(arr[left++]);\n        return res;\n    }\n\n```\n# slide window + binary search : (two pointers expand to K)\n```\n    //Runtime: 5 ms, faster than 90.39% of Java online submissions for Find K Closest Elements.\n    //Memory Usage: 44.5 MB, less than 88.75% of Java online submissions for Find K Closest Elements.\n    //slide window + binary search : (two pointers expand to K)\n    //Time: O(lgN + K); Space:O(1)\n    public List<Integer> findClosestElements_SlideWindow2(int[] arr, int k, int x) {\n\n        List<Integer> res = new LinkedList<>();\n\n\t\t//find the center\n        //Time: O(lgN)\n        //Binary search\n        int left = 0, right = arr.length, mid = 0;\n        while (left < right) {\n            mid = (right + left) / 2;\n            if (arr[mid] >= x) right = mid;\n            else left = mid + 1;\n        }\n        left--;\n        right = left + 1;\n\n        //Binary search\n//        int left = Arrays.binarySearch(arr, 0, arr.length, x);\n//        if (left < 0) left = Math.abs(left) - 2;\n//        int right = left + 1;\n\n        //Time: O(K)\n        while (right - left < k + 1) {\n            if (left == -1) {\n                res.add(arr[right++]);\n                continue;\n            }\n            //expand the window size\n            if (right >= arr.length || Math.abs(arr[left] - x) <= Math.abs(arr[right] - x))\n                res.add(0,arr[left--]);\n            else\n                res.add(arr[right++]);\n        }\n        return res;\n    }\n```\n# Slide window : (two pointers shrink to K)\n```\n    //Runtime: 4 ms, faster than 94.54% of Java online submissions for Find K Closest Elements.\n    //Memory Usage: 44.1 MB, less than 95.57% of Java online submissions for Find K Closest Elements.\n    //Slide window : (two pointers shrink to K)\n    //Time: O(N); Space: O(1)\n    public List<Integer> findClosestElements_SlideWindow1(int[] arr, int k, int x) {\n\n        List<Integer> res = new LinkedList<>();\n        int left = 0, right = arr.length - 1;\n\n        while (right - left > k - 1){\n            //shrink the window size from N to K\n            if (Math.abs(arr[left] - x) <= Math.abs(arr[right] - x))\n                right--;\n            else left++;\n        }\n        while (left <= right) res.add(arr[left++]);\n        return res;\n    }\n\n```\n# Sort With Custom Comparator\n```\n    //Runtime: 33 ms, faster than 28.49% of Java online submissions for Find K Closest Elements.\n    //Memory Usage: 44.7 MB, less than 87.04% of Java online submissions for Find K Closest Elements.\n    //29ms, 45.3mb\n    //Sort With Custom Comparator\n    //Time: O(N + N * logN + K * logK); Space: O(N + logN + logK)\n    public List<Integer> findClosestElements_sort2(int[] arr, int k, int x) {\n\n        //Space: O(N)\n        List<Integer> res = new LinkedList<>();\n\n        //Time: O(N)\n        for (int num : arr) res.add(num);\n        //Time: O(N * logN); Space: O(logN)\n        Collections.sort(res, Comparator.comparingInt(num -> Math.abs(num - x)));\n\n        res = res.subList(0, k);\n        //Time: O(K * logK); Space: O(logK)\n        Collections.sort(res);\n        return res;\n    }\n\n    //29ms, 45.3mb\n    //Sort With Custom Comparator\n    //Time: O(N + N * logN + K + K * logK); Space: O(N + logN + logK)\n    public List<Integer> findClosestElements_sort1(int[] arr, int k, int x) {\n        //Time: O(N); Space: O(N)\n        int[][] data = new int[arr.length][2];\n        for (int i = 0; i < arr.length; i++){\n            data[i][0] = arr[i];\n            data[i][1] = i;\n        }\n\n        //Time: O(N * logN); Space: O(logN)\n        Arrays.sort(data, (o1, o2) -> {\n            int a = Math.abs(o1[0] - x);\n            int b = Math.abs(o2[0] - x);\n            if (a == b) return o1[1] - o2[1];\n            return a - b;\n        });\n\n        //Time: O(K + K * logK); Space: O(logK)\n        List<Integer> res = new LinkedList<>();\n        for (int i = 0; i < k; i++) res.add(data[i][0]);\n        Collections.sort(res);\n        return res;\n    }\n```
['Binary Search', 'Sliding Window', 'Sorting', 'Java']