aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-05 20:04:59 -0600
committerJack Sangdahl <[email protected]>2024-09-05 20:04:59 -0600
commit9d6572995c179068d603e9ac90019bb736dfd51b (patch)
tree12fdbf762e4c6b384e715b0bbfc2f7de0995052b
parenta8cd949394a582f8c8c4717b6def6f5041f921be (diff)
downloadleetcode-9d6572995c179068d603e9ac90019bb736dfd51b.tar.gz
leetcode-9d6572995c179068d603e9ac90019bb736dfd51b.zip
658. find k closest elements
-rw-r--r--find_k_closest_elements.c38
-rw-r--r--find_k_closest_elements.cpp35
-rw-r--r--find_k_closest_elements.py32
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))