C++ O(N) solution 99% with explanation
Because we need kth greatest elements, in no particular order, we can simply use selection algorithms (such as quickselect, implemented as nth_element) to solve
Because we need `k`th greatest elements, in no particular order, we can simply use selection algorithms (such as quickselect, implemented as `nth_element`) to solve the problem in linear time. We first calculate the median using a selection algorithm which is `O(N)`. Then, we apply the selection algorithm again to find the element at `k`, using the given criteria as comparison. As a side effect of this selection algorithm, all numbers will be sorted according to the criteria, such that those with indices less than `k` will have greater "power". This is again `O(N)`. Then, we can simply take the array from `0` to `k` to get the solution, which is also `O(N)`. Thus, the overall run-time of this algorithm is `O(N)`. \n\n```\nclass Solution {\npublic:\n    vector<int> getStrongest(vector<int>& arr, int k) {\n        int size{(int)arr.size()}, m;\n        nth_element(arr.begin(), arr.begin()+((size-1)>>1), arr.end());\n        m = arr[(size-1)>>1];\n        nth_element(arr.begin(), arr.begin()+k, arr.end(), [&](const auto& a, const auto& b){return abs(a-m) == abs(b-m) ? a > b : abs(a-m) > abs(b-m);});\n        return std::vector<int>(arr.begin(), arr.begin()+k);\n    }\n};\n```
[]