leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1471.cpp (913B)

0 class Solution { 1 public: 2 vector<int> getStrongest(vector<int> &arr, int k) { 3 const int half = (arr.size() - 1) / 2; 4 nth_element(begin(arr), begin(arr) + half, end(arr)); 5 const int median = arr[half]; 6 nth_element(begin(arr), begin(arr) + k, end(arr), [&](int a, int b) { 7 return abs(a - median) != abs(b - median) ? abs(a - median) > abs(b - median) : a > b; 8 }); 9 arr.resize(k); 10 return arr; 11 } 12 }; 13 14 // Two pointer 15 class Solution { 16 public: 17 vector<int> getStrongest(vector<int> &arr, int k) { 18 sort(begin(arr), end(arr)); 19 const int median = arr[(arr.size() - 1) / 2]; 20 int i = 0, j = arr.size() - 1; 21 while (k--) 22 if (median - arr[i] > arr[j] - median) 23 i++; 24 else 25 j--; 26 arr.erase(begin(arr) + i, begin(arr) + j + 1); 27 return arr; 28 } 29 };