SHARE
TWEET

Untitled

bbescos Feb 23rd, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <limits>
  12.  
  13. using namespace std;
  14.  
  15. // Find k largest element (k = n/2)
  16.  
  17. void PrintVector(const vector<int>& nums) {
  18.     for (int i = 0; i < nums.size(); ++i) {
  19.         std::cout << nums[i] << " ";
  20.     }
  21.     std::cout << std::endl;
  22. }
  23.  
  24. int MedianUtil(vector<int>& nums, int left, int right, int k) {
  25.    
  26.     if (k > 0 && k <= (right - left + 1)) {
  27.        
  28.         int pivot = nums[right];
  29.         int j = left - 1;
  30.         for (int i = left; i <= right - 1; ++i) {
  31.             if (nums[i] <= pivot) {
  32.                 ++j;
  33.                 swap(nums[i], nums[j]);
  34.             }
  35.         }
  36.         ++j;
  37.         swap(nums[j], nums[right]);
  38.        
  39.         if (j - left == k - 1)
  40.             return nums[j];
  41.         if (j - left > k - 1)
  42.             return MedianUtil(nums, left, j - 1, k);
  43.  
  44.         return MedianUtil(nums, j + 1, right, k - j + left - 1);
  45.     }
  46.    
  47.     return numeric_limits<int>::min();
  48. }
  49.  
  50. int Median(vector<int>& nums) {
  51.    
  52.     return MedianUtil(nums, 0, nums.size() - 1, nums.size() / 2);
  53.    
  54. }
  55.  
  56. int main()
  57. {
  58.     vector<int> nums{0,2,3,1,6,4};
  59.     // 1 1 2 2 3 6
  60.     PrintVector(nums);
  61.    
  62.     std::cout << Median(nums) << std::endl;
  63.  
  64.     return 0;
  65. }
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
 
Top