SHARE
TWEET

Untitled

bbescos Feb 24th, 2019 44 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <limits>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. // Find the median of a vector<int>
  9.  
  10. void PrintVector(const vector<int>& nums) {
  11.     for (int i = 0; i < nums.size(); ++i)
  12.         std::cout << nums[i] << " ";
  13.     std::cout << std::endl;
  14. }
  15.  
  16. int MedianUtil(vector<int>& nums, int left, int right, int k) {
  17.    
  18.     if (k > 0 && k <= (right - left + 1)) {
  19.        
  20.         int pivot = nums[right];
  21.         int j = left - 1;
  22.         for (int i = left; i <= right - 1; ++i) {
  23.             if (nums[i] <= pivot) {
  24.                 ++j;
  25.                 swap(nums[i], nums[j]);
  26.             }
  27.         }
  28.         ++j;
  29.         swap(nums[j], nums[right]);
  30.        
  31.         if (j - left == k - 1)
  32.             return nums[j + 1];
  33.         if (j - left > k - 1)
  34.             return MedianUtil(nums, left, j - 1, k);
  35.  
  36.         return MedianUtil(nums, j + 1, right, k - j + left - 1);
  37.     }
  38.    
  39.     return numeric_limits<int>::min();
  40. }
  41.  
  42. /*
  43. int Median(vector<int>& nums) {
  44.     return MedianUtil(nums, 0, nums.size() - 1, nums.size() / 2);
  45. }
  46. */
  47.  
  48. int Median(vector<int>& nums) {
  49.     nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end(), [](const int p1, const int p2){return (p1 < p2);});
  50.     return(nums[nums.size() / 2]);
  51. }
  52.  
  53. int main()
  54. {
  55.     vector<int> nums{3, 2, 1, 6, 6};
  56.  
  57.     PrintVector(nums);
  58.    
  59.     std::cout << Median(nums) << std::endl;
  60.  
  61.     return 0;
  62. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top