vivek_ragi

K_CLOSEST_ELEMENTS

Jun 16th, 2021
533
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     //f(i) = abs(a[i] - x)
  4.     // g(i) = f(i) <= f(i+k)
  5.     // 00 111111
  6.     //TC: O(log(n-k))
  7.     vector<int> findClosestElements(vector<int>& arr, int k, int x) {
  8.         int n = arr.size();
  9.        
  10.         int lo = 0;
  11.         int hi = n - k;
  12.         int mid;
  13.         while(lo < hi)
  14.         {
  15.             mid = lo + (hi - lo)/2;
  16.            
  17.             if(x - arr[mid]  > arr[mid+k] - x)
  18.             {
  19.                 lo = mid + 1;
  20.             }
  21.             else
  22.             {
  23.                 hi = mid;
  24.             }
  25.         }
  26.        
  27.         return vector<int>(arr.begin() + lo, arr.begin() + lo + k);
  28.     }
  29. };
RAW Paste Data