diff options
author | Jack Sangdahl <[email protected]> | 2024-09-05 20:04:59 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-05 20:04:59 -0600 |
commit | 9d6572995c179068d603e9ac90019bb736dfd51b (patch) | |
tree | 12fdbf762e4c6b384e715b0bbfc2f7de0995052b | |
parent | a8cd949394a582f8c8c4717b6def6f5041f921be (diff) | |
download | leetcode-9d6572995c179068d603e9ac90019bb736dfd51b.tar.gz leetcode-9d6572995c179068d603e9ac90019bb736dfd51b.zip |
658. find k closest elements
-rw-r--r-- | find_k_closest_elements.c | 38 | ||||
-rw-r--r-- | find_k_closest_elements.cpp | 35 | ||||
-rw-r--r-- | find_k_closest_elements.py | 32 |
3 files changed, 98 insertions, 7 deletions
diff --git a/find_k_closest_elements.c b/find_k_closest_elements.c new file mode 100644 index 0000000..4a8e217 --- /dev/null +++ b/find_k_closest_elements.c @@ -0,0 +1,38 @@ +// 658. Find K Closest Elements +#include "leetcode.h" + +/* + * given a sorted integer array 'arr', two integers 'k' and 'x', return the 'k' + * closest integers to 'x' in the array. the result should also be sorted in + * ascending order. an integer 'a' is closer to 'x' than an integer 'b' if '|a - + * x| < |b - x|' or '|a - x| == |b - x|' and 'a < b'. + */ + +int *findClosestElements(int *arr, int arrSize, int k, int x, int *returnSize) { + int l = 0, r = arrSize - k; + while (l < r) { + int m = (l + r) / 2; + if (x - arr[m] > arr[m + k] - x) + l = m + 1; + else + r = m; + } + int *k_closest = (int *)calloc(k, sizeof(int)); + *returnSize = k; + for (int i = 0; i < k; i++) + k_closest[i] = arr[l++]; + return k_closest; +} + +int main() { + int a1[] = {1, 2, 3, 4, 5}, a2[] = {1, 2, 3, 4, 5}, rs1, rs2; + int *fce1 = findClosestElements(a1, ARRAY_SIZE(a1), 4, 3, &rs1); + int *fce2 = findClosestElements(a2, ARRAY_SIZE(a2), 4, -1, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", fce1[i]); // expect: 1 2 3 4 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", fce2[i]); // expect: 1 2 3 4 + printf("\n"); + free(fce1), free(fce2); +} diff --git a/find_k_closest_elements.cpp b/find_k_closest_elements.cpp index ecc1f53..e15810c 100644 --- a/find_k_closest_elements.cpp +++ b/find_k_closest_elements.cpp @@ -1,16 +1,37 @@ +// 658. Find K Closest Elements #include "leetcode.h" +/* + * given a sorted integer array 'arr', two integers 'k' and 'x', return the 'k' + * closest integers to 'x' in the array. the result should also be sorted in + * ascending order. an integer 'a' is closer to 'x' than an integer 'b' if '|a - + * x| < |b - x|' or '|a - x| == |b - x|' and 'a < b'. + */ + class Solution { public: vector<int> findClosestElements(vector<int> &arr, int k, int x) { - int left = 0, right = arr.size() - k; - while (left < right) { - int mid = (left + right) / 2; - if (x - arr[mid] > arr[mid + k] - x) - left = mid + 1; + int l = 0, r = arr.size() - k; + while (l < r) { + int m = (l + r) / 2; + if (x - arr[m] > arr[m + k] - x) + l = m + 1; else - right = mid; + r = m; } - return vector<int>(arr.begin() + left, arr.begin() + left + k); + return vector<int>(arr.begin() + l, arr.begin() + l + k); } }; + +int main() { + Solution obj; + vector<int> a1 = {1, 2, 3, 4, 5}, a2 = {1, 2, 3, 4, 5}; + vector<int> fce1 = obj.findClosestElements(a1, 4, 3); + vector<int> fce2 = obj.findClosestElements(a2, 4, -1); + for (int i = 0; i < fce1.size(); i++) + printf("%d ", fce1[i]); // expect: 1 2 3 4 + printf("\n"); + for (int i = 0; i < fce2.size(); i++) + printf("%d ", fce2[i]); // expect: 1 2 3 4 + printf("\n"); +} diff --git a/find_k_closest_elements.py b/find_k_closest_elements.py new file mode 100644 index 0000000..966895c --- /dev/null +++ b/find_k_closest_elements.py @@ -0,0 +1,32 @@ +# 658. Find K Closest Elements + +""" +given a sorted integer array 'arr', two integers 'k' and 'x', return the 'k' +closest integers to 'x' in the array. the result should also be sorted in +ascending order. an integer 'a' is closer to 'x' than an integer 'b' if '|a - +x| < |b - x|' or '|a - x| == |b - x|' and 'a < b'. +""" + + +class Solution(object): + def findClosestElements(self, arr, k, x): + """ + :type arr: List[int] + :type k: int + :type x: int + :rtype: List[int] + """ + l, r = 0, len(arr) - k + while l < r: + m = (l + r) / 2 + if x - arr[m] > arr[m + k] - x: + l = m + 1 + else: + r = m + return arr[l : l + k] + + +if __name__ == "__main__": + obj = Solution() + print(obj.findClosestElements(arr=[1, 2, 3, 4, 5], k=4, x=3)) + print(obj.findClosestElements(arr=[1, 2, 3, 4, 5], k=4, x=-1)) |