leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1471.cpp (913B)

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