leetcode

commit 7b16cedecc012943af1852b4903ba8777bc5de74
parent b6970a28a0b14b8d0923fb398d36acca71ff439c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 13 Oct 2023 18:09:48 +0000

Random Problem

Diffstat:
A
Problems/1471.cpp
 | 
30
++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 31 insertions(+), 0 deletions(-)
diff --git a/Problems/1471.cpp b/Problems/1471.cpp
@@ -0,0 +1,30 @@
+class Solution {
+  public:
+    vector<int> getStrongest(vector<int> &arr, int k) {
+        const int half = (arr.size() - 1) / 2;
+        nth_element(begin(arr), begin(arr) + half, end(arr));
+        const int median = arr[half];
+        nth_element(begin(arr), begin(arr) + k, end(arr), [&](int a, int b) {
+            return abs(a - median) != abs(b - median) ? abs(a - median) > abs(b - median) : a > b;
+        });
+        arr.resize(k);
+        return arr;
+    }
+};
+
+// Two pointer
+class Solution {
+  public:
+    vector<int> getStrongest(vector<int> &arr, int k) {
+        sort(begin(arr), end(arr));
+        const int median = arr[(arr.size() - 1) / 2];
+        int i = 0, j = arr.size() - 1;
+        while (k--)
+            if (median - arr[i] > arr[j] - median)
+                i++;
+            else
+                j--;
+        arr.erase(begin(arr) + i, begin(arr) + j + 1);
+        return arr;
+    }
+};
diff --git a/README.md b/README.md
@@ -626,6 +626,7 @@ for solving problems.
 |  1462  |   Medium   | [Course Schedule IV](Problems/1462.cpp)                                                            |
 |  1466  |   Medium   | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp)                        |
 |  1470  |    Easy    | [Shuffle the Array](Problems/1470.cpp)                                                             |
+|  1471  |   Medium   | [The k Strongest Values in an Array](Problems/1471.cpp)                                            |
 |  1472  |   Medium   | [Design Browser History ](Problems/1472.cpp)                                                       |
 |  1476  |   Medium   | [Subrectangle Queries](Problems/1476.cpp)                                                          |
 |  1480  |    Easy    | [Running Sum of 1d Array](Problems/1480.cpp)                                                       |