C++ | QuickSelect | Faster than 99.86%
Naive Approach:\n1. Sort the array in non-decreasing order.\n2. Choose median as (n-1)/2th element.\n3. Sort again based on a criteria given in question.\n\nMy 
Naive Approach:\n1. Sort the array in non-decreasing order.\n2. Choose median as (n-1)/2th element.\n3. Sort again based on a criteria given in question.\n\n**My Naive Approach Code:** (940 ms, faster than 39%)\n```\nclass Solution {\npublic:\n    int median;\n    vector<int> getStrongest(vector<int>& arr, int k) {\n        \n\t\tcin.tie(0);\n\t\tios_base::sync_with_stdio(false);\n\t\t\n        sort(arr.begin(), arr.end());\n        int n = arr.size();\n        \n        median = arr[(n-1)/2];\n        \n        sort(arr.begin(), arr.end(), [this](int a, int b){\n            if(abs(a - median) != abs(b - median)) return abs(a - median) > abs(b - median);\n           return a > b;\n        });\n        \n        arr.resize(k);\n        return arr;\n    }\n};\n```\n\nWhat are we missing?\nDo we really need to sort the full array?\nOr do we need to find the (n-1/)2th element for finding median, \nand the first k elements after the question criteria given.\n\nWe will use **quickselect** to acheive these tasks in O(n) time. (Worst case O(n^2)).\n\nQuickSelect is basically a partial sort in which we choose a pivot and then keep all smaller elements to the left, and bigger to the right.(We only need this in the question)\n\n\n1. For Finding the median\n\n\tChoose **Pivot**  = (n-1)/2.\n\tQuickselect keeps smaller elements in left, bigger in right.\n\tSo arr[n-1/2] will be the median (as defined by question)\n\n2. For finding the kth strongest\n\t\n\tChoose **Pivot** = k.\n\tWe will use a custom comparator such that quickselect keeps greater elements to left and lower to right.\n\tFirst k elements will be the strongest.\n\t\n\t\n**My Quick Select Code:** (256ms, faster than 99.86%)\n\n```\nclass Solution {\npublic:\n    int median;\n    vector<int> getStrongest(vector<int>& arr, int k) {\n\t\n\t\tcin.tie(0);\n\t\tios_base::sync_with_stdio(false);\n\t\t\n        int n = arr.size();\n        \n\t\t// A STL method in C++ for quick select.\n\t\t// Pivot is the (n-1)/2 th element.\n        nth_element(arr.begin(), arr.begin() + (n-1)/2, arr.end());\n        \n        median = arr[(n-1)/2];\n        \n\t\t// choose pivot = k and custom comparator to do as the question asks.\n        nth_element(arr.begin(),arr.begin() + k, arr.end(), [this](int a, int b){\n            if(abs(a - median) != abs(b - median)) return abs(a - median) > abs(b - median);\n           return a > b;\n        });\n        \n\t\t// return  the first k entries of output array.\n\t\t// Since the order of the answer does not matter, we can simply return the final answer.\n        vector<int> ans;\n        for(int i=0;i<k;i++) ans.push_back(arr[i]);\n        return ans;\n    }\n};\n```\n\nThanks and Happy Leetcoding!\n\n
[]